A note on domination, girth and minimum degree

Let G be a graph of order n, minimum degree δ?2, girth g?5 and domination number γ. In 1990 Brigham and Dutton [Bounds on the domination number of a graph, Q. J. Math., Oxf. II. Ser. 41 (1990) 269-275] proved that γ?⌈n/2-g/6⌉. This result was recently improved by Volkmann [Upper bounds on the domination number of a graph in terms of diameter and girth, J. Combin. Math. Combin. Comput. 52 (2005) 131-141; An upper bound for the domination number of a graph in terms of order and girth, J. Combin. Math. Combin. Comput. 54 (2005) 195-212] who for i∈{1,2} determined a finite set of graphs G_i such that γ?⌈n/2-g/6-(3i+3)/6⌉ unless G is a cycle or G∈G_i.Our main result is that for every i∈N there is a finite set of graphs G_i such that γ?n/2-g/6-i unless G is a cycle or G∈G_i. Furthermore, we conjecture another improvement of Brigham and Dutton's bound and prove a weakened version of this conjecture.     

Strong edge colorings of uniform graphs

For a graph G=(V(G),E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χ_s(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n,p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χ_s(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0<ε?d<1, all (d,ε)-regular bipartite graphs G=(U∪V,E) with |U|=|V|?n₀(d,ε) satisfy χ_s(G)?ζ(ε)Δ(G)², where ζ(ε)→0 as ε→0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24).     

Induced embeddings in Steinhaus graphs

Fix any positive integer n. Let S be the set of all Steinhaus graphs of order n(n − 1)/2 + 1. The vertices for each graph in S are the first n(n − 1)/2 + 1 positive integers. Let I be the set of all labeled graphs of order n with vertices of the form i(i − 1)/2 + 1 for the first n positive integers i. This article shows that the function ϕ : S → I that maps a Steinhaus graph to its induced subgraph is a bijection. Therefore, any graph of order n is isomorphic to an induced subgraph of a Steinhaus graph of order n(n − 1)/2 + 1. This considerably tightens a result of Brigham, Carrington, and Dutton in [Brigham, Carrington, & Dutton, Combin. Inform. System Sci. 17 (1992)], which showed that this could be done with a Steinhaus graph of order 2ⁿ⁻¹. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 1–9, 1998     

On the Ramsey Number of Sparse 3-Graphs

We consider a hypergraph generalization of a conjecture of Burr and Erd?s concerning the Ramsey number of graphs with bounded degree. It was shown by Chvátal, Rödl, Trotter, and Szemerédi [The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), no. 3, 239–243] that the Ramsey number R(G) of a graph G of bounded maximum degree is linear in |V(G)|. We derive the analogous result for 3-uniform hypergraphs.     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

Maximum non-path-connected graphs

Let n and i be integers with n ≥ 4 and 2 ≤ i ≤ n ? 1. Lewin (J. Combin. Theory Ser. B25 (1978), 245–257) has determined the smallest size of a connected n-graph without end vertices which ensures the existence of a path of length i between every pair of distinct vertices of the graph. Here all the connected n-graps without end vertices of maximum size are found which fail to have a path of length i between every pair of distinct vertices.     

Relative colorings of graphs

In this paper, the notion of relative chromatic number χ(G, H) for a pair of graphs G, H, with H a full subgraph of G, is formulated; namely, χ(G, H) is the minimum number of new colors needed to extend any coloring of H to a coloring of G. It is shown that the four color conjecture (4CC) is equivalent to the conjecture (R4CC) that χ(G, H) ≤ 4 for any (possibly empty) full subgraph H of a planar graph G and also to the conjecture (CR3CC) that χ(G, H) ≤ 3 if H is a connected and nonempty full subgraph of planar G. Finally, relative coloring theorems on surfaces other than the plane or sphere are proved.     

Incidence coloring of the squares of some graphs

The incidence chromatic number of G, denoted by χ_i(G), is the least number of colors such that G has an incidence coloring. In this paper, we determine the incidence chromatic number of the powers of paths, trees, which are min{n,2k+1}, and Δ(T²)+1, respectively. For the square of a Halin graph, we give an upper bound of its incidence chromatic number.     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.     

On a conjecture by Plummer and Toft

The cyclic chromatic number χ_c(G) of a 2‐connected plane graph G is the minimum number of colors in an assigment of colors to the vertices of G such that, for every face‐bounding cycle f of G, the vertices of f have different colors. Plummer and Toft proved that, for a 3‐connected plane graph G, under the assumption Δ*(G) ≥ 42, where Δ*(G) is the size of a largest face of G, it holds that χ_c(G) ≤ Δ*(G) + 4. They conjectured that, if G is a 3‐connected plane graph, then χ_c>(G) ≤ Δ*(G) + 2. In the article the conjecture is proved for Δ*(G) ≥ 24. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 177–189, 1999     

Equitable coloring of random graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ₌(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ₌*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n^?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n^?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ₌*(G(n,p)) = O_?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Closure, stability and iterated line graphs with a 2-factor

We consider 2-factors with a bounded number of components in the n-times iterated line graph Lⁿ(G). We first give a characterization of graph G such that Lⁿ(G) has a 2-factor containing at most k components, based on the existence of a certain type of subgraph in G. This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs Lⁿ(G) is stable under the closure operation on a claw-free graph G. This extends results in [Z. Ryjá?ek, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224; Z. Ryjá?ek, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117; L. Xiong, Z. Ryjá?ek, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104-115].     

Hamiltonian connectedness in 3-connected line graphs

We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.     

On domination and independent domination numbers of a graph

For a graph G, the definitions of domination number, denoted γ(G), and independent domination number, denoted i(G), are given, and the following results are obtained:Theorem.If G does not have an induced subgraph isomorphic to K_1,3, thenγ(G) = i(G).Corollary 1.For any graph G, γ(L(G))=i(L(G)), where L(G) is the line graph of G. (This extends the result γ(L(T))=i(L(T)), where T is a tree. Hedetniemi and Mitchell, S. E. Conf. Baton Rouge, 1977.)Corollary 2.For any Graph G, γ(M(G))=i(M(G)), where M is the middle graph of G.     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

Representing abstract groups by powers of a graph

We deal with the problem of representing several abstract groups simultaneously by one graph as automorphism groups of its powers. We call subgroups Γ₁,…, Γ_n of a finite group Γ representable iff there is a graph G and an injective mapping φ from ∪_i=1ⁿΓ_i into the symmetric group on V(G) such that for i=1,…, n φ|_Γi is a monomorphism onto Aut Gⁱ. We give a necessary and a sufficient condition for groups being representable, the latter implying, e.g., that finite groups Γ₁≤…≤Γ_n are representable.     

Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).     

The graph of perfect matching polytope and an extreme problem

For graph G, its perfect matching polytope Poly(G) is the convex hull of incidence vectors of perfect matchings of G. The graph corresponding to the skeleton of Poly(G) is called the perfect matching graph of G, and denoted by PM(G). It is known that PM(G) is either a hypercube or hamilton connected [D.J. Naddef, W.R. Pulleyblank, Hamiltonicity and combinatorial polyhedra, J. Combin. Theory Ser. B 31 (1981) 297-312; D.J. Naddef, W.R. Pulleyblank, Hamiltonicity in (0-1)-polytope, J. Combin. Theory Ser. B 37 (1984) 41-52]. In this paper, we give a sharp upper bound of the number of lines for the graphs G whose PM(G) is bipartite in terms of sizes of elementary components of G and the order of G, respectively. Moreover, the corresponding extremal graphs are constructed.