Home About us Contact
|
Home About us Contact | ||
|
|
||
Connected Graph (connected + graph)
Terms modified by Connected Graph Selected AbstractsA structure theorem for graphs with no cycle with a unique chord and its consequencesJOURNAL OF GRAPH THEORY, Issue 1 2010Nicolas Trotignon Abstract We give a structural description of the class ,, of graphs that do not contain a cycle with a unique chord as an induced subgraph. Our main theorem states that any connected graph in ,, is either in some simple basic class or has a decomposition. Basic classes are chordless cycles, cliques, bipartite graphs with one side containing only nodes of degree 2 and induced subgraphs of the famous Heawood or Petersen graph. Decompositions are node cutsets consisting of one or two nodes and edge cutsets called 1-joins. Our decomposition theorem actually gives a complete structure theorem for ,,, i.e. every graph in ,, can be built from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations, and all graphs built this way are in ,,. This has several consequences: an ,,(nm) -time algorithm to decide whether a graph is in ,,, an ,,(n+ m) -time algorithm that finds a maximum clique of any graph in ,,, and an ,,(nm) -time coloring algorithm for graphs in ,,. We prove that every graph in ,, is either 3-colorable or has a coloring with , colors where , is the size of a largest clique. The problem of finding a maximum stable set for a graph in ,, is known to be NP-hard. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 31,67, 2010 [source] Total domination in 2-connected graphs and in graphs with no induced 6-cyclesJOURNAL OF GRAPH THEORY, Issue 1 2009Michael A. Henning Abstract A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number ,t(G) of G. It is known [J Graph Theory 35 (2000), 21,45] that if G is a connected graph of order n,>,10 with minimum degree at least 2, then ,t(G),,,4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2-connected graphs, as well as for connected graphs with no induced 6-cycle. We prove that if G is a 2-connected graph of order n,>,18, then ,t(G),,,6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n,>,18 with minimum degree at least 2 and no induced 6-cycle, then ,t(G),,,6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55,79, 2009 [source] Between ends and fibersJOURNAL OF GRAPH THEORY, Issue 2 2007C. Paul Bonnington Abstract Let , be an infinite, locally finite, connected graph with distance function ,. Given a ray P in , and a constant C , 1, a vertex-sequence is said to be regulated by C if, for all n,,, never precedes xn on P, each vertex of P appears at most C times in the sequence, and . R. Halin (Math. Ann., 157, 1964, 125,137) defined two rays to be end-equivalent if they are joined by infinitely many pairwise-disjoint paths; the resulting equivalence classes are called ends. More recently H. A. Jung (Graph Structure Theory, Contemporary Mathematics, 147, 1993, 477,484) defined rays P and Q to be b-equivalent if there exist sequences and VQ regulated by some constant C , 1 such that for all n,,; he named the resulting equivalence classes b-fibers. Let denote the set of nondecreasing functions from into the set of positive real numbers. The relation (called f-equivalence) generalizes Jung's condition to . As f runs through , uncountably many equivalence relations are produced on the set of rays that are no finer than b -equivalence while, under specified conditions, are no coarser than end-equivalence. Indeed, for every , there exists an "end-defining function" that is unbounded and sublinear and such that implies that P and Q are end-equivalent. Say if there exists a sublinear function such that . The equivalence classes with respect to are called bundles. We pursue the notion of "initially metric" rays in relation to bundles, and show that in any bundle either all or none of its rays are initially metric. Furthermore, initially metric rays in the same bundle are end-equivalent. In the case that , contains translatable rays we give some sufficient conditions for every f -equivalence class to contain uncountably many g -equivalence classes (where ). We conclude with a variety of applications to infinite planar graphs. Among these, it is shown that two rays whose union is the boundary of an infinite face of an almost-transitive planar map are never bundle- equivalent. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 125,153, 2007 [source] Hamiltonian N2 -locally connected claw-free graphsJOURNAL OF GRAPH THEORY, Issue 2 2005Hong-Jian Lai Abstract A graph G is N2 - locally connected if for every vertex , in G, the edges not incident with , but having at least one end adjacent to , in G induce a connected graph. In 1990, Ryjá,ek conjectured that every 3-connected N2 -locally connected claw-free graph is Hamiltonian. This conjecture is proved in this note. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 142,146, 2005 [source] On possible counterexamples to Negami's planar cover conjectureJOURNAL OF GRAPH THEORY, Issue 3 2004Petr Hlin Abstract A simple graph H is a cover of a graph G if there exists a mapping , from H onto G such that , maps the neighbors of every vertex , in H bijectively to the neighbors of , (,) in G. Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. The conjecture is still open. It follows from the results of Archdeacon, Fellows, Negami, and the first author that the conjecture holds as long as the graph K1,2,2,2 has no finite planar cover. However, those results seem to say little about counterexamples if the conjecture was not true. We show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. Moreover, we exhibit a finite list of sets of graphs such that the set of excluded minors for the property of having finite planar cover is one of the sets in our list. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 183,206, 2004 [source] Graham's pebbling conjecture on products of cyclesJOURNAL OF GRAPH THEORY, Issue 2 2003David 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] Another two graphs with no planar coversJOURNAL OF GRAPH THEORY, Issue 4 2001Petr Hlin Abstract A graph H is a cover of a graph G if there exists a mapping , from V(H) onto V(G) such that , maps the neighbors of every vertex , in H bijectively to the neighbors of ,(,) in G. Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. It follows from the results of Archdeacon, Fellows, Negami, and the author that the conjecture holds as long as K1,2,2,2 has no finite planar cover. However, this is still an open question, and K1,2,2,2 is not the only minor-minimal graph in doubt. Let ,,4 (,2) denote the graph obtained from K1,2,2,2 by replacing two vertex-disjoint triangles (four edge-disjoint triangles) not incident with the vertex of degree 6 with cubic vertices. We prove that the graphs ,,4 and ,2 have no planar covers. This fact is used in [P. Hlin,ný, R. Thomas, On possible counterexamples to Negami's planar cover conjecture, 1999 (submitted)] to show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 227,242, 2001 [source] Sufficient conditions for a graph to be super restricted edge-connectedNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2008Shiying Wang Abstract Restricted edge connectivity is a more refined network reliability index than edge connectivity. A restricted edge cut F of a connected graph G is an edge cut such that G - F has no isolated vertex. The restricted edge connectivity ,, is the minimum cardinality over all restricted edge cuts. We call G ,,-optimal if ,, = ,, where , is the minimum edge degree in G. Moreover, a ,,-optimal graph G is called a super restricted edge-connected graph if every minimum restricted edge cut separates exactly one edge. Let D and g denote the diameter and girth of G, respectively. In this paper, we first present a necessary condition for non-super restricted edge-connected graphs with minimum degree , , 3 and D , g , 2. Next, we prove that a connected graph with minimum degree , , 3 and D , g , 3 is super restricted edge-connected. Finally, we give some sufficient conditions on the conditional diameter and the girth for super restricted edge-connected graphs. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008 [source] The proof of a conjecture of Bouabdallah and SotteauNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2004Min Xu Abstract Let G be a connected graph of order n. A routing in G is a set of n(n , 1) fixed paths for all ordered pairs of vertices of G. The edge-forwarding index of G, ,(G), is the minimum of the maximum number of paths specified by a routing passing through any edge of G taken over all routings in G, and ,,,n is the minimum of ,(G) taken over all graphs of order n with maximum degree at most ,. To determine ,n,2p,1,n for 4p + 2,p/3, + 1 , n , 6p, A. Bouabdallah and D. Sotteau proposed the following conjecture in [On the edge forwarding index problem for small graphs, Networks 23 (1993), 249,255]. The set 3 × {1, 2, , , ,(4p)/3,} can be partitioned into 2p pairs plus singletons such that the set of differences of the pairs is the set 2 × {1, 2, , , p}. This article gives a proof of this conjecture and determines that ,n,2p,1,n is equal to 5 if 4p + 2,p/3, + 1 , n , 6p and to 8 if 3p + ,p/3, + 1 , n , 3p + ,(3p)/5, for any p , 2. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 292,296 2004 [source] Total domination in 2-connected graphs and in graphs with no induced 6-cyclesJOURNAL OF GRAPH THEORY, Issue 1 2009Michael A. Henning Abstract A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number ,t(G) of G. It is known [J Graph Theory 35 (2000), 21,45] that if G is a connected graph of order n,>,10 with minimum degree at least 2, then ,t(G),,,4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2-connected graphs, as well as for connected graphs with no induced 6-cycle. We prove that if G is a 2-connected graph of order n,>,18, then ,t(G),,,6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n,>,18 with minimum degree at least 2 and no induced 6-cycle, then ,t(G),,,6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55,79, 2009 [source] Proof of Mader's conjecture on k -critical n -connected graphsJOURNAL OF GRAPH THEORY, Issue 4 2004Su Jianji Abstract Mader conjectured that every k -critical n -connected noncomplete graph G has 2k,+,2 pairwise disjoint fragments. The author in 9 proved that the conjecture holds if the order of G is greater than (k,+,2)n. Now we settle this conjecture completely. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 281,297, 2004 [source] Nowhere-zero 3-flows in locally connected graphsJOURNAL OF GRAPH THEORY, Issue 3 2003Hong-Jian Lai Abstract Let G be a graph. For each vertex v ,V(G), Nv denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k -edge-connected if for each vertex v ,V(G), Nv is k -edge-connected. In this paper we study the existence of nowhere-zero 3-flows in locally k -edge-connected graphs. In particular, we show that every 2-edge-connected, locally 3-edge-connected graph admits a nowhere-zero 3-flow. This result is best possible in the sense that there exists an infinite family of 2-edge-connected, locally 2-edge-connected graphs each of which does not have a 3-NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211,219, 2003 [source] On the fault-tolerant diameter and wide diameter of ,-connected graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2005Jian-Hua Yin Abstract The fault-tolerant diameter, Dk, and wide diameter, dk, are two important parameters for measuring the reliability and efficiency of interconnection networks. It is well known that for any ,-connected graph G and any integer k, 1 , k , ,, we have Dk , dk. However, what we are interested in is how large the difference between dk and Dk can be. For any 2-connected graph G with diameter d, Flandrin and Li proved that d2 , D2 + 1 if d = 2 and d2 , (d , 1)(D2 , 1) if d , 3. In this article, we further prove that d2 , max{D2 + 1, (d , 1)(D2 , d) + 2} for d , ,(D2 , 1)/2, and d2 , max{D2 + 1,,(D2 , 1)2/4, + 2} for d , ,(D2 , 1)/2, + 1, and we also show that this upper bound can be achieved. Moreover, for any ,(, 3)-connected graph G, we prove that d, , D, + 1 if D, , 1 = 2 and d, , max{D, + 2,,(D,)2/4, + 2} if D, , 1 = 2 and D, , 1 , 3. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 88,94 2005 [source] All-port line broadcasting in highly connected graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2005Iris Gaber Abstract In this article we propose polynomial time broadcasting protocols for an undirected graph under the circuit switched all-port model. In this model one vertex initiates a message and must inform all vertices of the graph of the message. The message is passed between the vertices of the graph in a sequence of rounds, where during a round the vertices communicate along edge disjoint paths. Our algorithms will require the graph to have a certain edge connectivity lower bound, to achieve fast broadcasting time. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 95,103 2005 [source] | ||||||||||