Moments of graphs in monotone families

The kth moment of the degree sequence d₁ ≥ d₂ ≥ …d_n of a graph G is . We give asymptotically sharp bounds for μ_k(G) when G is in a monotone family. We use these results for the case k = 2 to improve a result of Pach, Spencer, and Tóth [15]. We answer a question of Erd?s [9] by determining the maximum variance of the degree sequence when G is a triangle‐free n‐vertex graph. © 2005 Wiley Periodicals, Inc.     

Upper total domination in claw‐free graphs

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 (other than itself). The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ_t(G). We establish bounds on Γ_t(G) for claw‐free graphs G in terms of the number n of vertices and the minimum degree δ of G. We show that if if , and if δ ≥ 5. The extremal graphs are characterized. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 148–158, 2003     

List colorings with measurable sets

The measurable list chromatic number of a graph G is the smallest number ξ such that if each vertex v of G is assigned a set L(v) of measure ξ in a fixed atomless measure space, then there exist sets such that each c(v) has measure one and for every pair of adjacent vertices v and v'. We provide a simpler proof of a measurable generalization of Hall's theorem due to Hilton and Johnson [J Graph Theory 54 (2007), 179–193] and show that the measurable list chromatic number of a finite graph G is equal to its fractional chromatic number. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 229–238, 2008     

Relationships between total domination,order, size,and maximum degree of graphs

A total dominating set, S, in a graph, G, has the property that every vertex in G is adjacent to a vertex in S. The total dominating number, γ_t(G) of a graph G is the size of a minimum total dominating set in G. Let G be a graph with no component of size one or two and with Δ(G) ≥ 3. In 6 , it was shown that |E(G)| ≤ Δ(G) (|V(G)|–γ_t(G)) and conjectured that |E(G)| ≤ (Δ(G)+3) (|V(G)|–γ_t(G))/2 holds. In this article, we prove that holds and that the above conjecture is false as there for every Δ exist Δ‐regular bipartite graphs G with |E(G)| ≥ (Δ+0.1 ln(Δ)) (|V(G)|–γ_t(G))/2. The last result also disproves a conjecture on domination numbers from 8 . © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 325–337, 2007     

Circular choosability via combinatorial Nullstellensatz

A p‐list assignment L of a graph G assigns to each vertex v of G a set of permissible colors. We say G is L‐(P, q)‐colorable if G has a (P, q)‐coloring h such that h(v) ? L(v) for each vertex v. The circular list chromatic number of a graph G is the infimum of those real numbers t for which the following holds: For any P, q, for any P‐list assignment L with , G is L‐(P, q)‐colorable. We prove that if G has an orientation D which has no odd directed cycles, and L is a P‐list assignment of G such that for each vertex v, , then G is L‐(P, q)‐colorable. This implies that if G is a bipartite graph, then , where is the maximum average degree of a subgraph of G. We further prove that if G is a connected bipartite graph which is not a tree, then . © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 190–204, 2008     

Extending an edge-coloring

When can a k-edge-coloring of a subgraph K of a graph G be extended to a k-edge-coloring of G? One necessary condition is that for all X ? E(G) - E(K), where μ_i(X) is the maximum cardinality of a subset of X whose union with the set of edges of K colored i is a matching. This condition is not sufficient in general, but is sufficient for graphs of very simple structure. We try to locate the border where sufficiency ends.     

The circular chromatic number of the Mycielskian of G

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G) + 1. Chang, Huang, and Zhu [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear] have investigated circular chromatic numbers of Mycielskians for several classes of graphs. In this article, we study circular chromatic numbers of Mycielskians for another class of graphs G. The main result is that χ_c(μ(G)) = χ(μ(G)), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As χ_c(G) = and χ(G) = , consequently, there exist graphs G such that χ_c(G) is as close to χ(G) − 1 as you want, but χ_c(μ(G)) = χ(μ(G)). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 63–71, 1999     

Further results on the maximum size of a hole in an incomplete t‐wise balanced design with specified minimum block size*

Kreher and Rees 3 proved that if h is the size of a hole in an incomplete balanced design of order υ and index λ having minimum block size , then, They showed that when t = 2 or 3, this bound is sharp infinitely often in that for each h ≥ t and each k ≥ t + 1, (t,h,k) ≠(3,3,4), there exists an ItBD meeting the bound. In this article, we show that this bound is sharp infinitely often for every t, viz., for each t ≥ 4 there exists a constant C_t > 0 such that whenever (h ? t)(k ? t ? 1) ≥ C_t there exists an ItBD meeting the bound for some λ = λ(t,h,k). We then describe an algorithm by which it appears that one can obtain a reasonable upper bound on C_t for any given value of t. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 256–281, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10014     

A sharp edge bound on the interval number of a graph

The interval number of a graph G, denoted by i(G), is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Namely, it is shown that i(G) ≤ + 1. It is also observed that the edge bound induces i(G) ≤ , where γ(G) is the genus of G. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 153–159, 1999     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Balloons,cut‐edges,matchings, and total domination in regular graphs of odd degree

A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}$ be the family of connected (2r+1)‐regular graphs with n vertices, and let ${{b}}={{max}}\{{{b}}({{G}}): {{G}}\in {\mathcal{F}}_{{{n}},{{r}}}\}$. For ${{G}}\in{\mathcal{F}}_{{{n}},{{r}}}$, we prove the sharp inequalities c(G)?[r(n?2)?2]/(2r²+2r?1)?1 and α′(G)?n/2?rb/(2r+1). Using b?[(2r?1)n+2]/(4r²+4r?2), we obtain a simple proof of the bound proved by Henning and Yeo. For each of these bounds and each r, the approach using balloons allows us to determine the infinite family where equality holds. For the total domination number γ_t(G) of a cubic graph, we prove γ_t(G)?n/2?b(G)/2 (except that γ_t(G) may be n/2?1 when b(G)=3 and the balloons cover all but one vertex). With α′(G)?n/2?b(G)/3 for cubic graphs, this improves the known inequality γ_t(G)?α′(G). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 116–131, 2010     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003     

On the oriented chromatic index of oriented graphs

A homomorphism from an oriented graph G to an oriented graph H is a mapping from the set of vertices of G to the set of vertices of H such that is an arc in H whenever is an arc in G. The oriented chromatic index of an oriented graph G is the minimum number of vertices in an oriented graph H such that there exists a homomorphism from the line digraph LD(G) of G to H (the line digraph LD(G) of G is given by V(LD(G)) = A(G) and whenever and ). We give upper bounds for the oriented chromatic index of graphs with bounded acyclic chromatic number, of planar graphs and of graphs with bounded degree. We also consider lower and upper bounds of oriented chromatic number in terms of oriented chromatic index. We finally prove that the problem of deciding whether an oriented graph has oriented chromatic index at most k is polynomial time solvable if k ≤ 3 and is NP‐complete if k ≥ 4. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 313–332, 2008     

Packing k‐edge trees in graphs of restricted vertex degrees

Let denote the set of graphs with each vertex of degree at least r and at most s, v(G) the number of vertices, and τ_k (G) the maximum number of disjoint k‐edge trees in G. In this paper we show that

• (a1) if G ∈ and s ≥ 4, then τ₂(G) ≥ v(G)/(s + 1),
• (a2) if G ∈ and G has no 5‐vertex components, then τ₂(G) ≥ v(G)4,
• (a3) if G ∈ and G has no k‐vertex component, where k ≥ 2 and s ≥ 3, then τ_k(G) ≥ (v(G) ‐k)/(sk ‐ k + 1), and
• (a4) the above bounds are attained for infinitely many connected graphs.

Our proofs provide polynomial time algorithms for finding the corresponding packings in a graph. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 306–324, 2007     

On Local Invertible Operators in L2 (ℝ1, H)

We study operators of the form Lu = — G(t) u(t) in L²([t₀ — δ, t₀ + δ], H) with = L² ([t₀— δ, t₀ + δ], H ) in the neighbourhood [t₀— δ, t₀ + δ] of a point t₀ ∈ ℝ¹. Such problems arise in questions on local solvability of partial differential equations (see [6] and [7]). For these operators,one of the major questions is if they are invertible in a neighbourhood of a point t ∈ ℝ¹. To solve this problem we establish needed commutator estimates. Using the commutator estimates and factorization theorems for nonanalytic operator-functions we give additional conditions for the nonanalytic operator -function G(t) and show that the operator L (or ) with some boundary conditions is local invertible.     

Rooted induced trees in triangle‐free graphs

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010     

The decomposition threshold for bipartite graphs with minimum degree one

Let H be a fixed bipartite graph with δ(H) = 1. It is shown that if G is any graph with n vertices and minimum degree at least ${n\over 2}\bigl(1 + o_n(1)\bigr)$ and e(H) divides e(G), then G can be decomposed into e(G)/e(H) edge‐disjoint copies of H. This is best possible and significantly extends the result of an earlier paper by the author [8] which deals with the case where H is a tree. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 121–134, 2002     

Cycle lengths in graphs with large minimum degree

Our main result is the following theorem. Let k ≥ 2 be an integer, G be a graph of sufficiently large order n, and δ(G) ≥ n/k. Then:

• (i) G contains a cycle of length t for every even integer t ∈ [4, δ(G) + 1].
• (ii) If G is nonbipartite then G contains a cycle of length t for every odd integer t ∈ [2k ? 1, δ(G) + 1], unless k ≥ 6 and G belongs to a known exceptional class.

© 2006 Wiley Periodicals, Inc. J Graph Theory 52: 157–170, 2006     

Spanning trees with many leaves

We show that if G is a simple connected graph with and , then G has a spanning tree with > t leaves, and this is best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 189–197, 2001     

Construction of graphs with given circular flow numbers

Suppose r ≥ 2 is a real number. A proper r‐flow of a directed multi‐graph is a mapping such that (i) for every edge , ; (ii) for every vertex , . The circular flow number of a graph G is the least r for which an orientation of G admits a proper r‐flow. The well‐known 5‐flow conjecture is equivalent to the statement that every bridgeless graph has circular flow number at most 5. In this paper, we prove that for any rational number r between 2 and 5, there exists a graph G with circular flow number r. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 304–318, 2003