On 3-Edge-Connected Supereulerian Graphs

The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995 that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d _G (u) + d _G (v) ≥ 9, then G has a spanning eulerian subgraph.     

A charcterization of 4-edge-connected eulerian graphs

Let v be an arbitrary vertex of a 4-edge-connected Eulerian graph G. First we show the existence of a nonseparating cycle decompositiion of G with respect to v. With the help of this decomposition we are then able to construct 4 edge-independent spanning trees with the common root v in the sam graph. We conclude that an Eulerian graph G is 4-edge-connected iff for every vertex r ? V (G) there exist 4 edge-independent spanning trees with a common root r. © 1996 John Wiley & Sons, Inc.     

On Spanning Disjoint Paths in Line Graphs

Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, 2009). For a graph G and an integer s > 0 and for ${u, v \in V(G)}$ with u ≠ v, an (s; u, v)-path-system of G is a subgraph H consisting of s internally disjoint (u,v)-paths. A graph G is spanning s-connected if for any ${u, v \in V(G)}$ with u ≠ v, G has a spanning (s; u, v)-path-system. The spanning connectivity κ*(G) of a graph G is the largest integer s such that G has a spanning (k; u, v)-path-system, for any integer k with 1 ≤ k ≤ s, and for any ${u, v \in V(G)}$ with u ≠ v. An edge counter-part of κ*(G), defined as the supereulerian width of a graph G, has been investigated in Chen et al. (Supereulerian graphs with width s and s-collapsible graphs, 2012). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207–222, 1991) proved that if a graph G has 2 edge-disjoint spanning trees, and if L(G) is the line graph of G, then κ*(L(G)) ≥ 2 if and only if κ(L(G)) ≥ 3. In this paper, we extend this result and prove that for any integer k ≥ 2, if G ₀, the core of G, has k edge-disjoint spanning trees, then κ*(L(G)) ≥ k if and only if κ(L(G)) ≥ max{3, k}.     

On Superconnectivity of (4, g)-Cages

A (k, g)-cage is a graph that has the least number of vertices among all k-regular graphs with girth g. It has been conjectured (Fu et?al. in J. Graph Theory, 24:187?C191, 1997) that all (k, g)-cages are k-connected for every k??? 3. A k-connected graph G is called superconnected if every k-cutset S is the neighborhood of some vertex. Moreover, if G?S has precisely two components, then G is called tightly superconnected. In this paper, we prove that every (4, g)-cage is tightly superconnected when g ???11 is odd.     

On (s,t)-supereulerian graphs in locally highly connected graphs

Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K₂ or to K_2,l with l odd.     

Edge-disjoint spanners in tori

A spanning subgraph S=(V,E^′) of a connected graph G=(V,E) is an (x+c)-spanner if for any pair of vertices u and v, d_S(u,v)≤d_G(u,v)+c where d_G and d_S are the usual distance functions in G and S, respectively. The parameter c is called the delay of the spanner. We study edge-disjoint spanners in graphs in multi-dimensional tori. We show that each two-dimensional torus has a set of two edge-disjoint spanners of delay approximately the size of the smaller dimension. Moreover, we show that this delay is close to the best possible. In three-dimensional tori, we find a set of three edge-disjoint spanners with delay approximately the sum of the sizes of the two smaller dimensions when all dimensions are of even size. Surprisingly, we also find a set of two edge-disjoint spanners in three-dimensional tori of constant delay. In d-dimensional tori, we show that for any k≤d/5, there is a set of k edge-disjoint spanners with delay depending only on k and the size of the smaller k dimensions.     

Paths and edge-connectivity in graphs

Mader proved that for every k-edge-connected graph G (k ≥ 4), there exists a path joining two given vertices such that the subgraph obtained from G by deleting the edges of the path is (k - 2)-edge-connected. A generalization of this and a sufficient condition for existance of 3, 4, or 5 terminus k edge-disjoint paths in graphs are given.     

Bounds on the number of disjoint spanning trees

It is shown that an n-edge connected graph has at least ?$\text{(n ? 1)}\text{2}$? pairwise edge-disjoint spanning trees. This bound is best possible in general. A maximal planar graph with four or more vertices contains two edge-disjoint spanning trees. For a maximal toroidal graph, this number is three.     

Orientations of infinite graphs with prescribed edge-connectivity

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.     

Packing and Covering Triangles in Planar Graphs

Tuza conjectured that if a simple graph G does not contain more than k pairwise edge-disjoint triangles, then there exists a set of at most 2k edges that meets all triangles in G. It has been shown that this conjecture is true for planar graphs and the bound is sharp. In this paper, we characterize the set of extremal planar graphs.     

Some remarks on the odd hadwiger’s conjecture

We say that H has an odd complete minor of order at least l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Gerards and Seymour conjectured that if a graph has no odd complete minor of order l, then it is (l ? 1)-colorable. This is substantially stronger than the well-known conjecture of Hadwiger. Recently, Geelen et al. proved that there exists a constant c such that any graph with no odd K _k -minor is ck√logk-colorable. However, it is not known if there exists an absolute constant c such that any graph with no odd K _k -minor is ck-colorable. Motivated by these facts, in this paper, we shall first prove that, for any k, there exists a constant f(k) such that every (496k + 13)-connected graph with at least f(k) vertices has either an odd complete minor of size at least k or a vertex set X of order at most 8k such that G–X is bipartite. Since any bipartite graph does not contain an odd complete minor of size at least three, the second condition is necessary. This is an analogous result of Böhme et al. We also prove that every graph G on n vertices has an odd complete minor of size at least n/2α(G) ? 1, where α(G) denotes the independence number of G. This is an analogous result of Duchet and Meyniel. We obtain a better result for the case α(G)= 3.     

Connectivity of iterated line graphs

Let k≥0 be an integer and L^k(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L²(G))≥4δ(G)−6. We show that the connectivity of G can be relaxed. In fact, we prove in this note that if G is an essentially 4-edge-connected and 3-connected graph, then κ(L²(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs.     

An approximate version of the Loebl-Komlós-Sós conjecture

Loebl, Komlós, and Sós conjectured that if at least half of the vertices of a graph G have degree at least some k∈N, then every tree with at most k edges is a subgraph of G. Our main result is an approximate version of this conjecture for large enough n=|V(G)|, assumed that n=O(k).Our result implies an asymptotic bound for the Ramsey number of trees. We prove that r(Tk,Tm)?k+m+o(k+m), as k+m→∞.     

On covering vertices of a graph by trees

The purpose of this paper is to initiate study of the following problem: Let G be a graph, and k?1. Determine the minimum number s of trees T₁,…,T_s, Δ(T_i)?k,i=1,…,s, covering all vertices of G. We conjecture: Let G be a connected graph, and k?2. Then the vertices of G can be covered by edge-disjoint trees of maximum degree ?k. As a support for the conjecture we prove the statement for some values of δ and k.     

An upper bound for the competition numbers of graphs

A hole of a graph is an induced cycle of length at least 4. Kim (2005) [2] conjectured that the competition number k(G) is bounded by h(G)+1 for any graph G, where h(G) is the number of holes of G. In Lee et al. [3], it is proved that the conjecture is true for a graph whose holes are mutually edge-disjoint. In Li et al. (2009) [4], it is proved that the conjecture is true for a graph, all of whose holes are independent. In this paper, we prove that Kim’s conjecture is true for a graph G satisfying the following condition: for each hole C of G, there exists an edge which is contained only in C among all induced cycles of G.     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

Sandpile groups and spanning trees of directed line graphs

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.     

Spanning trees with leaf distance at least four

For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007     

The competition number of a graph whose holes do not overlap much

Let D be an acyclic digraph. The competition graph of D is a graph which has the same vertex set as D and has an edge between u and v if and only if there exists a vertex x in D such that (u,x) and (v,x) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices.A hole of a graph is an induced cycle of length at least four. Kim (2005) [8] conjectured that the competition number of a graph with h holes is at most h+1. Recently, Li and Chang (2009) [11] showed that the conjecture is true when the holes are independent. In this paper, we show that the conjecture is true though the holes are not independent but mutually edge-disjoint.