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.     

Dissections, Hom-complexes and the Cayley trick

We show that certain canonical realizations of the complexes Hom(G,H) and Hom₊(G,H) of (partial) graph homomorphisms studied by Babson and Kozlov are, in fact, instances of the polyhedral Cayley trick. For G a complete graph, we then characterize when a canonical projection of these complexes is itself again a complex, and exhibit several well-known objects that arise as cells or subcomplexes of such projected Hom-complexes: the dissections of a convex polygon into k-gons, Postnikov's generalized permutohedra, staircase triangulations, the complex dual to the lower faces of a cyclic polytope, and the graph of weak compositions of an integer into a fixed number of summands.     

An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph

A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to υ, where uυ ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ′ _aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G(V, E) is a graph with no isolated edges, then χ′ _aa (G) ≤ 32Δ. Supported by the Natural Science Foundation of Gansu Province (3ZS051-A25-025)     

Bounds on the Total Restrained Domination Number of a Graph

Let G = (V, E) be a graph. A set S í V{S \subseteq V} is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ _tr (G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ _tr (G) ≤ n − diam(G) − r + 1.     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

On the adjacent vertex-distinguishing acyclic edge coloring of some graphs

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by x′ _Aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.     

Some results on R 2-edge-connectivity of even regular graphs

Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given.     

The diameter of paired-domination vertex critical graphs

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set of G. The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one, γ _pr(G − v) < γ _pr(G). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least 3/2 (γ _pr(G) − 2). For γ _pr(G) ⩽ 8, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph. The first author was supported in part by the South African National Research Foundation and the University of KwaZulu-Natal, the second author was supported by the Natural Sciences and Engineering Research Council of Canada.     

T-Colorings and T-Edge Spans of Graphs

 Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that |f(x)−f(y)|∉T whenever xy∈E(G). The edge span of a T-coloring−f is the maximum value of |f(x) f(y)| over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C ^d _n of the n-cycle C _n for T={0, 1, 2, …, k−1}. In particular, we find the exact value of the T-edge span of C _n ^d for n≡0 or (mod d+1), and lower and upper bounds for other cases. Received: May 13, 1996 Revised: December 8, 1997     

Set vertex colorings and joins of graphs

For a nontrivial connected graph G, let c: V (G) → ℕ be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ NC(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number x _s (G). A study is made of the set chromatic number of the join G+H of two graphs G and H. Sharp lower and upper bounds are established for x _s (G + H) in terms of x _s (G), x _s (H), and the clique numbers ω(G) and ω(H).     

Bounds on the Distance Two-Domination Number of a Graph

 For a graph G = (V, E), a subset D⊆V(G) is said to be distance two-dominating set in G if for each vertex u∈V−D, there exists a vertex v∈D such that d(u,v)≤2. The minimum cardinality of a distance two-dominating set in G is called a distance two-domination number and is denoted by γ₂(G). In this note we obtain various upper bounds for γ₂(G) and characterize the classes of graphs attaining these bounds. Received: May 31, 1999 Final version received: July 13, 2000     

Up-embeddability via girth and the degree-sum of adjacent vertices

Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d _G (u) + d _G (v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d _G (u) + d _G (v) ⩾ n − 2g + 3 (resp. d _G (u) + d _G (v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight. This work was supported by National Natural Science Foundation of China (Grant No. 10571013)     

On second order degree of graphs

Given a vertex v of a graph G the second order degree of v denoted as d 2(v) is defined as the number of vertices at distance 2 from v.In this paper we address the following question:What are the sufficient conditions for a graph to have a vertex v such that d2(v) ≥ d(v),where d(v) denotes the degree of v? Among other results,every graph of minimum degree exactly 2,except four graphs,is shown to have a vertex of second order degree as large as its own degree.Moreover,every K-4-free graph or every maximal planar graph is shown to have a vertex v such that d2(v) ≥ d(v).Other sufficient conditions on graphs for guaranteeing this property are also proved.     

Trees with Equal Domination and Restrained Domination Numbers

Let G = (V,E) be a graph and let S V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set S is a dominating set (DS) if every vertex in V − S is adjacent to a vertex in S. Further, if every vertex in V − S is also adjacent to a vertex in V − S, then S is a restrained dominating set (RDS). The domination number of G, denoted by γ(G), is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T)=γ_r(T); (ii) T is a γ-excellent tree and T ≠ K₂; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γ_r(T) ≤ (n + ℓ + 1)/2, and we characterize those trees achieving equality.     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

Homotopy groups of Hom complexes of graphs

The notion of ×-homotopy from [Anton Dochtermann, Hom complexes and homotopy theory in the category of graphs, European J. Combin., in press] is investigated in the context of the category of pointed graphs. The main result is a long exact sequence that relates the higher homotopy groups of the space Hom_∗(G,H) with the homotopy groups of Hom_∗(G,HI). Here Hom_∗(G,H) is a space which parameterizes pointed graph maps from G to H (a pointed version of the usual Hom complex), and HI is the graph of based paths in H. As a corollary it is shown that πi(Hom_∗(G,H))≅_×[G,ΩiH], where ΩH is the graph of based closed paths in H and _×[G,K] is the set of ×-homotopy classes of pointed graph maps from G to K. This is similar in spirit to the results of [Eric Babson, Hélène Barcelo, Mark de Longueville, Reinhard Laubenbacher, Homotopy theory of graphs, J. Algebraic Combin. 24 (1) (2006) 31-44], where the authors seek a space whose homotopy groups encode a similarly defined homotopy theory for graphs. The categorical connections to those constructions are discussed.     

Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

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.     

Potentially <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> — <Emphasis Type="Italic">G</Emphasis>-graphical sequences: A survey

The set of all non-increasing nonnegative integer sequences π = (d(v ₁), d(v ₂), …, d(v _n )) is denoted by NS _n . A sequence π ∈ NS _n is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of π. The set of all graphic sequences in NS _n is denoted by GS _n . A graphical sequence π is potentially H-graphical if there is a realization of π containing H as a subgraph, while π is forcibly H-graphical if every realization of π contains H as a subgraph. Let K _k denote a complete graph on k vertices. Let K _m −H be the graph obtained from Km by removing the edges set E(H) of the graph H (H is a subgraph of K _m ). This paper summarizes briefly some recent results on potentially K _m −G-graphic sequences and give a useful classification for determining σ (H, n).