Home  About us  Contact
 

One Vertex (one + vertex)

Distribution by Scientific Domains
Mathematics and Statistics85%

Selected Abstracts

Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs

JOURNAL OF GRAPH THEORY, Issue 4 2003
Zhi-Hong Chen
Abstract In this paper, we show that if G is a 3-edge-connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3-edge-connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308,319, 2003 [source]

Graham's pebbling conjecture on products of cycles

JOURNAL OF GRAPH THEORY, Issue 2 2003
David S. Herscovici
Abstract Chung defined a pebbling move on a graph G to be the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graph is the smallest number f(G) such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphs G and H, f(G×H), f(G)f(H). We prove Graham's conjecture when G is a cycle for a variety of graphs H, including all cycles. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 141,154, 2003 [source]

On factors of 4-connected claw-free graphs,

JOURNAL OF GRAPH THEORY, Issue 2 2001
H. J. Broersma
Abstract We consider the existence of several different kinds of factors in 4-connected claw-free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4-connected line graph is hamiltonian, i.e., has a connected 2-factor. Conjecture 2 (Matthews and Sumner): Every 4-connected claw-free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass-free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125,136, 2001 [source]

A branch-and-cut algorithm for partition coloring

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2010
Yuri Frota
Abstract Let G = (V, E, Q) be a undirected graph, where V is the set of vertices, E is the set of edges, and Q = {Q1,,,Qq} is a partition of V into q subsets. We refer to Q1,,,Qq as the components of the partition. The partition coloring problem (PCP) consists of finding a subset V, of V with exactly one vertex from each component Q1,,,Qq and such that the chromatic number of the graph induced in G by V, is minimum. This problem is a generalization of the graph coloring problem. This work presents a branch-and-cut algorithm proposed for PCP. An integer programing formulation and valid inequalities are proposed. A tabu search heuristic is used for providing primal bounds. Computational experiments are reported for random graphs and for PCP instances originating from the problem of routing and wavelength assignment in all-optical WDM networks. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source]

Minimum multiple message broadcast graphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2006
Hovhannes A. Harutyunyan
Abstract Multiple message broadcasting is the process of multiple message dissemination in a communication network in which m messages, originated by one vertex, are transmitted to all vertices of the network. A graph G with n vertices is called a m-message broadcast graph if its broadcast time is the theoretical minimum. Bm(n) is the minimum number of edges in any m-message broadcast graph on n vertices. An m-message minimum broadcast graph is a broadcast graph G on n vertices having Bm(n) edges. This article presents several lower and upper bounds on Bm(n). In particular, it is shown that modified Knödel graphs are m-message broadcast graphs for m , min,log n,,n , 2,log n,. From the Cartesian product of some broadcast graphs we obtain better upper bounds on Bm(n), and in some cases we can prove that Bm(n) = O(n). The exact value of B2(2k) is also established. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 218,224 2006 [source]

Fixed tree games with multilocated players

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2006
S. Miquel
Abstract This article introduces fixed tree games with multilocated players (FMP games), which are a generalization of standard fixed tree games. This generalization consists of allowing players to be located in more than one vertex. As a consequence, these players can choose among several ways of connection to the root. In this article we show that FMP games are balanced. Moreover, we prove that the core of an FMP game coincides with the core of a related submodular standard fixed tree game. We show how to find the nucleolus and we characterize the orders that provide marginal vectors in the core of an FMP game. Finally, we study the Shapley value and the average of the extreme points of the core. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 93,101 2006 [source]

Three-periodic nets and tilings: minimal nets

ACTA CRYSTALLOGRAPHICA SECTION A, Issue 6 2004
Charlotte Bonneau
The 15 3-periodic minimal nets of Beukemann & Klee [Z. Kristallogr. (1992), 201, 37,51] have been examined. Seven have collisions in barycentric coordinates and are self-entangled. The other eight have natural tilings. Five of these tilings are self-dual and the nets are the labyrinth nets of the P, G, D, H and CLP minimal surfaces of genus 3. Twelve ways have been found for subdividing a cube into smaller tiles without introducing new vertices. Duals of such tilings with one vertex in the primitive cell have nets that are one of the minimal nets. Minimal nets without collisions are uniform. [source]