Claw‐decompositions and tutte‐orientations

We conjecture that, for each tree T, there exists a natural number k_T such that the following holds: If G is a k_T‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K_1,3 (the claw), this holds if and only if there exists a (smallest) natural number k_t such that every k_t‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that k_t = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006     

A cycle cover of a 2-edge-connected graph embedded with large face-width on an orientable surface

In 1985, Alon and Tarsi conjectured that the length of a shortest cycle cover of a bridgeless graph H is at most 7/5 |E(H|). The conjecture is still open. Let G be a 2-edge-connected graph embedded with face-width k on the non-spherical orientable surface S_g. We give an upper bound on the length of a cycle cover of G. In particular, if g = 1 and k ≥ 48, or g = 2 and k ≥ 427, or g ≥ 3 and k ≥ 288(4^g - 1), then the upper bound is 7/5 |E(G|), which means that Alon and Tarsi’s conjecture holds for such a graph.     

Decomposing a graph into bistars

Bárat and the present author conjectured that, for each tree T  , there exists a natural number _kT$k_T$ such that the following holds: If G   is a _kT$k_T$-edge-connected graph such that |E(T)|$|E(T)|$ divides |E(G)|$|E(G)|$, then G has a T-decomposition, that is, a decomposition of the edge set into trees each of which is isomorphic to T  . The conjecture has been verified for infinitely many paths and for each star. In this paper we verify the conjecture for an infinite family of trees that are neither paths nor stars, namely all the bistars S(k,k+1)$S(k,k+1)$.     

Competitively Tight Graphs

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) 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 a graph G is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph G is related to the edge clique cover number θ _E (G) of the graph G via θ _E (G) ? |V(G)| + 2 ≤ k(G) ≤ θ _E (G). We first show that for any positive integer m satisfying 2 ≤ m ≤ |V(G)|, there exists a graph G with k(G) = θ _E (G) ? |V(G)| + m and characterize a graph G satisfying k(G) = θ _E (G). We then focus on what we call competitively tight graphs G which satisfy the lower bound, i.e., k(G) = θ _E (G) ? |V(G)| + 2. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.     

Adjacent strong edge coloring of graphs

For a graph G(V, E), if a proper k-edge coloring ƒ is satisfied with C(u) ≠ C(v) for uv ∈ E(G), where $\text{C(u) = {ƒ(uv) | uv ∈ E}}$, then ƒ is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC, and χ′_as(G) = min{k | k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper, we discuss some properties of χ′_as(G), and obtain the χ′_as(G) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ′_as(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G.     

Bisecting a 4-connected graph with three resource sets

Let G=(V,E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T₁,T₂,…,T_k of nodes, called resource sets, where |T_i| is even for each i. The partition problem with k resource sets asks to find a partition V₁ and V₂ of the node set V such that the graphs induced by V₁ and V₂ are both connected and |V₁∩T_i|=|V₂∩T_i|=|T_i|/2 holds for each i=1,2,…,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that if G is (k+1)-connected for k=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for k?3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k=3, the conjecture does not hold, while if G is 4-connected and has K₄ as its subgraph, then a bisection exists and it can be found in O(|V|³log|V|) time. Moreover, we show that for an arc-version of the problem, the (k+1)-edge-connectivity suffices for k=1,2,3.     

On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

A degree sum condition for long cycles passing through a linear forest

Let G be a (k+m)-connected graph and F be a linear forest in G such that |E(F)|=m and F has at most k-2 components of order 1, where k?2 and m?0. In this paper, we prove that if every independent set S of G with |S|=k+1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min{d-m,|V(G)|} which contains all the vertices and edges of F.     

A generalization of Fan’s results: Distribution of cycle lengths in graphs

Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(C_k)|−|E(C_k−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if d_G(u)+d_G(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if d_G(u)+d_G(v)≥6k+1, then |E(C_k)|−|E(C_k−1)|=2.     

Spanning Connectivity of the Power of a Graph and Hamilton-Connected Index of a Graph

Let G = (V, E) be a connected graph. The hamiltonian index h(G) (Hamilton-connected index hc(G)) of G is the least nonnegative integer k for which the iterated line graph L ^k (G) is hamiltonian (Hamilton-connected). In this paper we show the following. (a) If |V(G)| ≥ k + 1 ≥ 4, then in G ^k , for any pair of distinct vertices {u, v}, there exists k internally disjoint (u, v)-paths that contains all vertices of G; (b) for a tree T,  h(T) ≤ hc(T) ≤ h(T) + 1, and for a unicyclic graph G,  h(G) ≤ hc(G) ≤ max{h(G) + 1, k′ + 1}, where k′ is the length of a longest path with all vertices on the cycle such that the two ends of it are of degree at least 3 and all internal vertices are of degree 2; (c) we also characterize the trees and unicyclic graphs G for which hc(G) = h(G) + 1.     

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.     

Cohomologie galoisienne des groupes quasi-déployés sur des corps de dimension cohomologique ≤2; Galois cohomology of quasi-split groups over fields of cohomological dimension ≤ 2

Let k be a perfect field with cohomological dimension 2. Serre's conjecture II claims that the Galois cohomology set H ¹(k,G) is trivial for any simply connected semi-simple algebraic G/k and this conjecture is known for groups of type ¹ A _n after Merkurjev–Suslin and for classical groups and groups of type F ₄ and G ₂ after Bayer–Parimala. For any maximal torus T of G/k, we study the map H ¹(k, T) H ¹(k, G) using an induction process on the type of the groups, and it yields conjecture II for all quasi-split simply connected absolutely almost k-simple groups with type distinct from E ₈. We also have partial results for E ₈ and for some twisted forms of simply connected quasi-split groups. In particular, this method gives a new proof of Hasse principle for quasi-split groups over number fields including the E ₈-case, which is based on the Galois cohomology of maximal tori of such groups.     

Distance graphs with maximum chromatic number

The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K₄.     

Comparing Zagreb indices for connected graphs

It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M₂(G)/m≥M₁(G)/n, where M₁ and M₂ are the first and second Zagreb indices. Hansen and Vuki?evi? proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that m−n=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M₂/(m−1)>M₁/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results.     

The entire graph of a bridgeless connected plane graph is hamiltonian

In this paper we show that the entire graph of a bridgeless connected plane graph is hamiltonian, and that the entire graph of a plane block is hamiltonian connected and vertex pancyclic. In addition, we show that in any block G which is not a circuit, given a vertex v of G and a circuit k of G, there is a path p, suspended in G, such that p is a path in k of length at least 1 and G ? E(p) ? V₀(G ? E(p)) is a block which includes v.     

Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph

The theory of vertex-disjoint cycles and 2-factors of graphs is the extension and generation of the well-known Hamiltonian cycles theory and it has important applications in network communication. In this paper we first prove the following result. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+1, where k≥1 is an integer. If d(x)+d(y)≥?(4n+2k?1)/3? for each pair of nonadjacent vertices x and y of G with x∈V ₁ and y∈V ₂, then, for any k independent edges e ₁,…,e _k of G, G contains k vertex-disjoint quadrilaterals C ₁,…,C _k such that e _i ∈E(C _i ) for each i∈{1,…,k}. We further show that the degree condition above is sharp. If |V ₁|=|V ₂|=2k, we give degree conditions that G has a 2-factor with k vertex-disjoint quadrilaterals C ₁,…,C _k containing specified edges of G.     

Covering a graph with cycles passing through given edges

We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e₁, …, e_k of G, there exist k vertex-disjoint cycles C₁, …, C_k in G such that e_i ∈ E(C_i) for all i ∈ {1, …, k} and V(C₁ ∪ ···∪ C_k) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

On the spanning connectivity of graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if it contains all vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. The spanning connectivity of G, κ^*(G), is defined to be the largest integer k such that G is w^*-connected for all 1?w?k if G is a 1^*-connected graph. In this paper, we prove that κ^*(G)?2δ(G)-n(G)+2 if (n(G)/2)+1?δ(G)?n(G)-2. Furthermore, we prove that κ^*(G-T)?2δ(G)-n(G)+2-|T| if T is a vertex subset with |T|?2δ(G)-n(G)-1.