Total domination in graphs with minimum degree three

A set S of vertices of a graph G is a total dominating set, if every vertex of V(G) is adjacent to some vertex in S. The total domination number of G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at least 3, then γ_t(G) ≤ 7n/13. © 2000 John Wiley & Sons, Inc. J Graph Theory 34:9–19, 2000     

On the number of list-colorings

Given a list of boxes L for a graph G (each vertex is assigned a finite set of colors that we call a box), we denote by f(G, L) the number of L-colorings of G (each vertex must be colored wiht a color of its box). In the case where all the boxes are identical and of size k, f(G, L) = p(G, k), where P=G, k) is the chromatic polynominal of G. We denote by F(G, k) the minimum of f(G, L) over all the lists of boxes such that each box has size at least k. It is clear that F(G, k) ≤ P(G, k) for all G, k, and we will see in the introduction some examples of graphs such that F(G, k) < P(G, k) for some k. However, we will show, in answer to a problem proposed by A. Kostochka and A. Sidorenko (Fourth Czechoslovak Symposium on Combinatorics, Prachatice, Jin, 1990), that for all G, F(G, k) = P(G, k) for all k sufficiently large. It will follow in particular that F(G, k) is not given by a polynominal in k for all G. The proof is based on the analysis of an algorithm for computing f(G, L) analogous to the classical one for computing P(G, k).     

Degrees and choice numbers

The choice number ch(G) of a graph G=(V, E) is the minimum number k such that for every assignment of a list S(v) of at least k colors to each vertex v∈V, there is a proper vertex coloring of G assigning to each vertex v a color from its list S(v). We prove that if the minimum degree of G is d, then its choice number is at least (½−o(1))log₂ d, where the o(1)‐term tends to zero as d tends to infinity. This is tight up to a constant factor of 2+o(1), improves an estimate established by the author, and settles a problem raised by him and Krivelevich. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 364–368, 2000     

List Coloring of Random and Pseudo-Random Graphs

choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most . Received: October 13, 1997     

Connected -tuple twin domination in de Bruijn and Kautz digraphs

For a digraph G, a k-tuple twin dominating set D of G for some fixed k≥1 is a set of vertices such that every vertex is adjacent to at least k vertices in D, and also every vertex is adjacent from at least k vertices in D. If the subgraph of G induced by D is strongly connected, then D is called a connected k-tuple twin dominating set of G. In this paper, we give constructions of minimal connected k-tuple twin dominating sets for de Bruijn digraphs and Kautz digraphs.     

Cycles in bipartite graphs

For k an integer, let G(a, b, k) denote a simple bipartite graph with bipartition (A, B) where |A| = a ≥ 2, |B| = b ≥ k ≥ 2, and each vertex of A has degree at least k. We prove two results concerning the existence of cycles in G(a, b, k).     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

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.     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

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. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

The <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-dominating set of the graph G is a subset D of V (G) such that every vertex of V (G)-D is adjacent to at least k vertices in D. A k-domatic partition of G is a partition of V (G) into k-dominating sets. The maximum number of dominating sets in a k-domatic partition of G is called the k-domatic number d _k (G). In this paper, we present upper and lower bounds for the k-domatic number, and we establish Nordhaus-Gaddum-type results. Some of our results extend those for the classical domatic number d(G) = d ₁(G).      

The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ _k (G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U₁,U₂ ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U ₁ and the other in U ₂ by [U ₁, U ₂]. Define x_k(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ _k -optimal if λ _k (G) = ξ _k (G). A graph is said to be super-λ _k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ _k -optimal or super-λ _k . Moreover, we demonstrate that our results are best possible.     

On the list dynamic coloring of graphs

A proper vertex coloring of a graph G is called a dynamic coloring if for every vertex v of degree at least 2, the neighbors of v receive at least two different colors. Assume that is the minimum number k such that for every list assignment of size k to each vertex of G, there is a dynamic coloring of G such that every vertex is colored with a color from its list. In this paper, it is proved that if G is a graph with no component isomorphic to C₅ and Δ(G)≥3, then , where Δ(G) is the maximum degree of G. This generalizes a result due to Lai, Montgomery and Poon which says that under the same assumptions χ₂(G)≤Δ(G)+1. Among other results, we determine , for every natural number n.     

On the size of graphs labeled with a condition at distance two

A labeling of graph G with a condition at distance two is an integer labeling of V(G) such that adjacent vertices have labels that differ by at least two, and vertices distance two apart have labels that differ by at least one. The lambda-number of G, λ(G), is the minimum span over all labelings of G with a condition at distance two. Let G(n, k) denote the set of all graphs with order n and lambda-number k. In this paper, we examine the sizes of graphs in G(n, k). We modify Chvàtal's result on non-hamiltonian graphs to obtain a formula for the minimum size of a graph in G(n, k), and we use an algorithmic approach to obtain a formula for the maximum size. Finally, we show that for any integer j between the maximum and minimum sizes there exists a graph with size j in G(n, k). © 1996 John Wiley & Sons, Inc.     

Dynamic list coloring of bipartite graphs

A dynamic coloring of a graph is a proper coloring of its vertices such that every vertex of degree more than one has at least two neighbors with distinct colors. The least number of colors in a dynamic coloring of G, denoted by χ₂(G), is called the dynamic chromatic number of G. The least integer k, such that if every vertex of G is assigned a list of k colors, then G has a proper (resp. dynamic) coloring in which every vertex receives a color from its own list, is called the choice number of G, denoted by ch(G) (resp. the dynamic choice number, denoted by ch₂(G)). It was recently conjectured (Akbari et al. (2009) [1]) that for any graph G, ch₂(G)=max(ch(G),χ₂(G)). In this short note we disprove this conjecture. We first give an example of a small planar bipartite graph G with ch(G)=χ₂(G)=3 and ch₂(G)=4. Then, for any integer k≥5, we construct a bipartite graph G_k such that ch(G_k)=χ₂(G_k)=3 and ch₂(G)≥k.     

A new domination conception

Let f be an integer valued function defined on the vertex set V(G) of a simple graph G. We call a subset D_f of V(G) a f-dominating set of G if |N(x, G) ∩ D_f| ≥ f(x) for all x ∈ V(G) — D_f, where N(x, G) is the set of neighbors of x. D_f is a minimum f-dominating set if G has no f-dominating set D′_f with |D_f| < |D_f|. If j, k ∈ N₀ = {0,1,2,…} with j ≤ k, then we define the integer valued function f_j,k on V(G) by . By μ_j,k(G) we denote the cardinality of a minimum f_j,k-dominating set of G. A set D ? V(G) is j-dominating if every vertex, which is not in D, is adjacent to at least j vertices of D. The j-domination number γ_j(G) is the minimum order of a j-dominating set in G. In this paper we shall give estimations of the new domination number μ_j,k(G), and with the help of these estimations we prove some new and some known upper bounds for the j-domination number. © 1993 John Wiley & Sons, Inc.     

Independent Trees and Branchings in Planar Multigraphs

 The following statement is proved: Let G be a finite directed or undirected planar multigraph and s be a vertex of G such that for each vertex x≠s of G, there are at least k pairwise openly disjoint paths in G from x to s where k∉{3,4,5} if G is directed. Then there exist k spanning trees T ₁, … ,T _k in G directed towards s if G is directed such that for each vertex x≠s of G, the k paths from x to s in T ₁, … ,T _k are pairwise openly disjoint. – The case where G is directed and k∈{3,4,5} remains open. Received: January 30, 1995 / Revised: October 7, 1996     

A Local Property of Large Polyhedral Maps on Compact 2-Dimensional Manifolds

We prove that each polyhedral map G on a compact 2-manifold, which has large enough vertices, contains a k-path, a path on k vertices, such that each vertex of it has, in G, degree at most 6k; this bound being best possible for k even. Moreover, if G has large enough vertices of degree >6k, than it contains a k-path such that each its vertex has degree, in G, at most 5k; this bound is best possible for any k. Received: December 8, 1997 Revised: April 27, 1998     

Conditional colorings of graphs

For an integer r>0, a conditional(k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least r in G will be adjacent to vertices with at least r different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is the rth order conditional chromatic number χ_r(G). In this paper, the behavior and bounds of conditional chromatic number of a graph G are investigated.     

A characterization of panconnected graphs satisfying a local ore-type condition

It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc.     

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