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).      

On the graph of large distances

For a setS of points in the plane, letd ₁>d ₂>... denote the different distances determined byS. Consider the graphG(S, k) whose vertices are the elements ofS, and two are joined by an edge iff their distance is at leastd _k . It is proved that the chromatic number ofG(S, k) is at most 7 if |S|constk ². IfS consists of the vertices of a convex polygon and |S|constk ², then the chromatic number ofG(S, k) is at most 3. Both bounds are best possible. IfS consists of the vertices of a convex polygon thenG(S, k) has a vertex of degree at most 3k – 1. This implies that in this case the chromatic number ofG(S, k) is at most 3k. The best bound here is probably 2k+1, which is tight for the regular (2k+1)-gon.     

On k -diameter of k -connected graphs

Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d _k (G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d _k (G). For a fixed positive integer d, some conditions to insure d _k (G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d _k (G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. Supported by NNSF of China (19971086).     

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.     

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     

On Moore bipartite digraphs

In the context of the degree/diameter problem for directed graphs, it is known that the number of vertices of a strongly connected bipartite digraph satisfies a Moore‐like bound in terms of its diameter k and the maximum out‐degrees (d₁, d₂) of its partite sets of vertices. It has been proved that, when d₁d₂ > 1, the digraphs attaining such a bound, called Moore bipartite digraphs, only exist when 2 ≤ k ≤ 4. This paper deals with the problem of their enumeration. In this context, using the theory of circulant matrices and the so‐called De Bruijn near‐factorizations of cyclic groups, we present some new constructions of Moore bipartite digraphs of diameter three and composite out‐degrees. By applying the iterated line digraph technique, such constructions also provide new families of dense bipartite digraphs with arbitrary diameter. Moreover, we show that the line digraph structure is inherent in any Moore bipartite digraph G of diameter k = 4, which means that G = L G′, where G′ is a Moore bipartite digraph of diameter k = 3. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 171–187, 2003     

A characterization of ptolemaic graphs

A connected graph G is ptolemaic provided that for each four vertices U_i, 1 ≤ i ≤ 4, of G, the six distances d_ii = d_G (U_i, U_i), i ≠ j satisfy the inequality d₁₂d₃₄ ≤ d₁₃d₂₄ + d₁₄d₂₃ (shown by Ptolemy to hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showed that weakly geodetic ptolemaic graphs are precisely Husimi trees (in particular, trees are ptolemaic). in the present paper several characterizations of ptolemaic graphs are given. It is shown, for example, that a connected graph G is ptolemaic if and only iffor each nondisjoint cliques P, Q of G, their intersection is a cutset of G which separates P-Q and Q-P. An operation is exhibited which generates all finite ptolemaic graphs from complete graphs.     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

An upper bound for the k-domination number of a graph

The k-domination number of a graph G, γk(G), is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k, then γk(G) ≤ kp/(k + 1).     

On graphs with small Ramsey numbers*

Let R(G) denote the minimum integer N such that for every bicoloring of the edges of K_N, at least one of the monochromatic subgraphs contains G as a subgraph. We show that for every positive integer d and each γ,0 < γ < 1, there exists k = k(d,γ) such that for every bipartite graph G = (W,U;E) with the maximum degree of vertices in W at most d and , . This answers a question of Trotter. We give also a weaker bound on the Ramsey numbers of graphs whose set of vertices of degree at least d + 1 is independent. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 198–204, 2001     

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.     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

Fan-type theorem for path-connectivity

A graphG is said to bek-path-connected if every pair of distinct vertices inG are joined by a path of length at leastk. We prove that if max{deg _G ^x , deg _G ^y }k for every pair of verticesx,y withd _G (x,y)=2 in a 2-connected graphG, whered _G (x,y) is the distance betweenx andy inG, thenG isk-path-connected.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

二部图的距离k次方和问题

本文定义S_k（G）为G中所有点对之间距离的k次方之和.利用顶点划分的方法得到了直径为d的n顶点连通二部图S_k（G）的下界,并确定了达到下界所对应的的极图.     

Coverings of the Vertices of a Graph by Small Cycles

Given a graph G with n vertices, we call c_k(G) the minimum number of elementary cycles of length at most k necessary to cover the vertices of G. We bound c_k(G) from the minimum degree and the order of the graph.     

Equitable Total Coloring of Graphs with Maximum Degree 3

 The equitable total chromatic number χr d q u o; _e (G) of a graph G is the smallest integer k for which G has a total k-coloring such that the number of vertices and edges in any two color classes differ by at most one. We prove in this paper that χr d q u o; _e (G)≤5 if G is a multigraph with maximum degree at most 3. Received: February 24, 2000 Final version received: February 2, 2001 Acknowledgments. The author would like to thank the referee for valuable suggestions to improve this work.     

Ordering Starlike Trees by the Totality of Their Spectral Moments

The k-th spectral moment M_k(G) of the adjacency matrix of a graph G represents the number of closed walks of length k in G. We study here the partial order ? of graphs, defined by G ? H if M_k(G) ≤ M_k(H) for all k ≥?0, and are interested in the question when is ? a linear order within a specified set of graphs? Our main result is that ? is a linear order on each set of starlike trees with constant number of vertices. Recall that a connected graph G is a starlike tree if it has a vertex u such that the components of G ? u are paths, called the branches of G. It turns out that the ? ordering of starlike trees with constant number of vertices coincides with the shortlex order of sorted sequence of their branch lengths.

     

The game chromatic number of random graphs

Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of G are colored. The game chromatic number χ_g(G) is the minimum k for which the first player has a winning strategy. In this study, we analyze the asymptotic behavior of this parameter for a random graph G_n,p. We show that with high probability, the game chromatic number of G_n,p is at least twice its chromatic number but, up to a multiplicative constant, has the same order of magnitude. We also study the game chromatic number of random bipartite graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Complete subgraphs with large degree sums

Let t(n, k) denote the Turán number—the maximum number of edges in a graph on n vertices that does not contain a complete graph K_k+1. It is shown that if G is a graph on n vertices with n ≥ k²(k – 1)/4 and m < t(n, k) edges, then G contains a complete subgraph K_k such that the sum of the degrees of the vertices is at least 2km/n. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of K_k is not in general larger, and if the number of edges in G is at most t(n, k) – ? (for an appropriate ?), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc.