Sharp bounds on distance spectral radius of graphs

Let D(G) denote the distance matrix of a connected graph G. The largest eigenvalue of D(G) is called the distance spectral radius of a graph G, denoted by ?(G). In this article, we give sharp upper and lower bounds for the distance spectral radius and characterize those graphs for which these bounds are best possible.     

Toughness and longest cycles in 2-connected planar graphs

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) ≥ βn^α for some positive constants β and α ≅ 0.2 if G is 3-connected. Now let G have connectivity 2. Then c(G) may be as small as 4, as with K_2,n-2, unless we bound w(G − S) for every subset S of V(G) with |S| = 2. Define ξ(G) as the maximum of w(G − S) taken over all 2-element subsets S ⊆ V(G). We give an asymptotically sharp lower bound for the toughness of G in terms of ξ(G), and we show that c(G) ≥ θ ln n for some positive constant θ depending only on ξ(G). In the proof we use a recent result of Gao and Yu improving Jackson and Wormald's result. Examples show that the lower bound on c(G) is essentially best-possible. © 1996 John Wiley & Sons, Inc.     

Pancyclic subgraphs of random graphs

An n‐vertex graph is called pancyclic if it contains a cycle of length t for all 3≤t≤n. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if p>n^?1/2, then the random graph G(n, p) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G(n, p) with more than edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich et al. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers). © 2011 Wiley Periodicals, Inc.     

Fragile graphs with small independent cuts

A graph is called fragile if it has a vertex cut which is also an independent set. Chen and Yu proved that every graph with n vertices and at most 2n?4 edges is fragile, which was conjectured to be true by Caro. However, their proof does not give any information on the number of vertices in the independent cuts. The purpose of this paper is to investigate when a graph has a small independent cut. We show that if G is a graph on n vertices and at most (12n/7)?3 edges, then G contains an independent cut S with ∣S∣≤3. Upper bounds on the number of edges of a graph having an independent cut of size 1 or 2 are also obtained. We also show that for any positive integer k, there is a positive number ε such that there are infinitely many graphs G with n vertices and at most (2?ε)n edges, but G has no independent cut with less than k vertices. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 327–341, 2002     

Clique-transversal sets in 4-regular claw-free graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by τ _c (G), is the minimum cardinality of a clique-transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.     

Long paths in sparse random graphs

We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc. Dedicated to Tibor Gallai on his seventieth birthday     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

Geometric graphs with no two parallel edges

We give a simple proof for a theorem of Katchalski, Last, and Valtr, asserting that the maximum number of edges in a geometric graph G on n vertices with no pair of parallel edges is at most 2n−2. We also give a strengthening of this result in the case where G does not contain a cycle of length 4. In the latter case we show that G has at most 3/2(n−1) edges.     

Balanced coloring of bipartite graphs

Given a bipartite graph G(U∪V, E) with n vertices on each side, an independent set I∈G such that |U∩I|=|V∩I| is called a balanced bipartite independent set. A balanced coloring of G is a coloring of the vertices of G such that each color class induces a balanced bipartite independent set in G. If graph G has a balanced coloring we call it colorable. The coloring number χ_B(G) is the minimum number of colors in a balanced coloring of a colorable graph G. We shall give bounds on χ_B(G) in terms of the average degree $\bar{d}$ of G and in terms of the maximum degree Δ of G. In particular we prove the following:

• $\chi_{{{B}}}({{G}}) \leq {{max}} \{{{2}},\lfloor {{2}}\overline{{{d}}}\rfloor+{{1}}\}$.
• For any 0<ε<1 there is a constant Δ₀ such that the following holds. Let G be a balanced bipartite graph with maximum degree Δ≥Δ₀ and n≥(1+ε)2Δ vertices on each side, then $\chi_{{{B}}}({{G}})\leq \frac{{{{20}}}}{\epsilon^{{{2}}}} \frac{\Delta}{{{{ln}}}\,\Delta}$.

© 2009 Wiley Periodicals, Inc. J Graph Theory 64: 277–291, 2010     

The critical random graph,with martingales

We give a short proof that the largest component C ₁ of the random graph G(n, 1/n) is of size approximately n ^2/3. The proof gives explicit bounds for the probability that the ratio is very large or very small. In particular, the probability that n ^−2/3|C ₁| exceeds A is at most e ^{- cA3}{e^{ - c{A^3}}} for some c > 0.     

Random lifts of graphs: Independence and chromatic number

For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χ_f, we show that the chromatic number of typical lifts is bounded from below by const ? and also by const ? χ_f/log²χ_f (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

Set intersection representations for almost all graphs

Two variations of set intersection representation are investigated and upper and lower bounds on the minimum number of labels with which a graph may be represented are found that hold for almost all graphs. Specifically, if θ_k(G) is defined to be the minimum number of labels with which G may be represented using the rule that two vertices are adjacent if and only if they share at least k labels, there exist positive constants c_k and c′_k such that almost every graph G on n vertices satisfies Changing the representation only slightly by defining θ;_odd (G) to be the minimum number of labels with which G can be represented using the rule that two vertices are adjacent if and only if they share an odd number of labels results in quite different behavior. Namely, almost every graph G satisfies Furthermore, the upper bound on θ_odd(G) holds for every graph. © 1996 John Wiley & Sons, Inc.     

On convex embeddings of planar 3‐connected graphs

A well‐known Tutte's theorem claims that every 3‐connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3‐connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in this embedding. We give a simple proof of this last result. Our proof is based on the fact that a 3‐connected graph admits an ear assembly having some special properties with respect to the nonseparating cycles of the graph. This fact may be interesting and useful in itself. © 2000 John Wiley & Sons, Inc. J. Graph Theory 33: 120–124, 2000     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Regular graphs whose subgraphs tend to be acyclic

Motivated by a problem that arises in the study of mirrored storage systems, we describe, for any fixed ε, δ > 0, and any integer d ≥ 2, explicit or randomized constructions of d‐regular graphs on n > n₀(ε, δ) vertices in which a random subgraph obtained by retaining each edge, randomly and independently, with probability , is acyclic with probability at least 1 ? δ. On the other hand we show that for any d‐regular graph G on n > n₁(ε, δ) vertices, a random subgraph of G obtained by retaining each edge, randomly and independently, with probability , does contain a cycle with probability at least 1 ? δ. The proofs combine probabilistic and combinatorial arguments, with number theoretic techniques. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Rank‐width of random graphs

Rank‐width of a graph G, denoted by rw (G), is a width parameter of graphs introduced by Oum and Seymour [J Combin Theory Ser B 96 (2006), 514–528]. We investigate the asymptotic behavior of rank‐width of a random graph G(n, p). We show that, asymptotically almost surely, (i) if p∈(0, 1) is a constant, then rw (G(n, p)) = ?n/3??O(1), (ii) if , then rw (G(n, p)) = ?1/3??o(n), (iii) if p = c/n and c>1, then rw (G(n, p))?rn for some r = r(c), and (iv) if p?c/n and c81, then rw (G(n, p))?2. As a corollary, we deduce that the tree‐width of G(n, p) is linear in n whenever p = c/n for each c>1, answering a question of Gao [2006]. © 2011 Wiley Periodicals, Inc. J Graph Theory.     

On Hamilton cycles in certain planar graphs

Let G be a 2-connected plane graph with outer cycle X_G such that for every minimal vertex cut S of G with |S| ≤ 3, every component of G\S contains a vertex of X_G. A sufficient condition for G to be Hamiltonian is presented. This theorem generalizes both Tutte's theorem that every 4-connected planar graph is Hamiltonian, as well as a recent theorem of Dillencourt about NST-triangulations. A linear algorithm to find a Hamilton cycle can be extracted from the proof. One corollary is that a 4-connected planar graph with the vertices of a triangle deleted is Hamiltonian. © 1996 John Wiley & Sons, Inc.     

On graphs with a given endomorphism monoid

Hedrlín and Pultr proved that for any monoid M there exists a graph G with endomorphism monoid isomorphic to M . In this paper we give a construction G(M) for a graph with prescribed endomorphism monoid M . Using this construction we derive bounds on the minimum number of vertices and edges required to produce a graph with a given endomorphism monoid for various classes of finite monoids. For example we show that for every monoid M , | M |=m there is a graph G with End(G)? M and |E(G)|≤(1 + 0(1))m². This is, up to a factor of 1/2, best possible since there are monoids requiring a graph with \begin{eqnarray*} && \frac{m^{2}}{2}(1 -0(1)) \end{eqnarray*} edges. We state bounds for the class of all monoids as well as for certain subclasses—groups, k‐cancellative monoids, commutative 3‐nilpotent monoids, rectangular groups and completely simple monoids. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 241–262, 2009     

List total colorings of series-parallel graphs

A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|min{5,Δ+1} for each vertex v and |L(e)|max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.