Pancyclicity mod k of claw-free graphs and K1,4-free graphs

For any natural number k, a graph G is said to be pancyclic mod k if it contains a cycle of every length modulo k. In this paper, we show that every K_1,4-free graph G with minimum degree δ(G)k+3 is pancyclic mod k and every claw-free graph G with δ(G)k+1 is pancyclic mod k, which confirms Thomassen's conjecture (J. Graph Theory 7 (1983) 261–271) for claw-free graphs.     

ContributionsUpper domination and upper irredundance perfect graphs

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is calledΓ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) = IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.     

Graphs having distance-n domination number half their order

For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ_=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson.     

Least domination in a graph

The least domination number γ_L of a graph G is the minimum cardinality of a dominating set of G whose domination number is minimum. The least point covering number _L of G is the minimum cardinality of a total point cover (point cover including every isolated vertex of G) whose total point covering number is minimum. We prove a conjecture of Sampathkumar saying that in every connected graph of order n 2. We disprove another one saying that γ_{L L} in every graph but instead of it, we establish the best possible inequality . Finally, in relation with the minimum cardinality γ_t of a dominating set without isolated vertices (total dominating set), we prove that the ratio γ_L/γ_t can be in general arbitrarily large, but remains bounded by if we restrict ourselves to the class of trees.     

Choosability conjectures and multicircuits

This paper starts with a discussion of several old and new conjectures about choosability in graphs. In particular, the list-colouring conjecture, that ch′=χ′ for every multigraph, is shown to imply that if a line graph is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t. It is proved that ch(H²)=χ(H²) for many “small” graphs H, including inflations of all circuits (connected 2-regular graphs) with length at most 11 except possibly length 9; and that ch″(C)=χ″(C) (the total chromatic number) for various multicircuits C, mainly of even order, where a multicircuit is a multigraph whose underlying simple graph is a circuit. In consequence, it is shown that if any of the corresponding graphs H² or T(C) is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t.     

No-hole L(2,1)-colorings

An L(2,1)-coloring of a graph G is a coloring of G's vertices with integers in {0,1,…,k} so that adjacent vertices’ colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span λ(G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is λ(G), and the hole index ρ(G) of G is the minimum number of colors in {0,1,…,λ(G)} not used in a span coloring. We say that G is full-colorable if ρ(G)=0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span μ(G) of G as ∞ if G has no no-hole coloring; otherwise μ(G) is the minimum k for which G has a no-hole coloring using colors in {0,1,…,k}.

Let n denote the number of vertices of G, and let Δ be the maximum degree of vertices of G. Prior work shows that all non-star trees with Δ3 are full-colorable, all graphs G with n=λ(G)+1 are full-colorable, μ(G)λ(G)+ρ(G) if G is not full-colorable and nλ(G)+2, and G has a no-hole coloring if and only if nλ(G)+1. We prove two extremal results for colorings. First, for every m1 there is a G with ρ(G)=m and μ(G)=λ(G)+m. Second, for every m2 there is a connected G with λ(G)=2m, n=λ(G)+2 and ρ(G)=m.     

ContributionsAcyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

Block graphs with unique minimum dominating sets

For any graph G a set D of vertices of G is a dominating set, if every vertex vV(G)−D has at least one neighbor in D. The domination number γ(G) is the smallest number of vertices in any dominating set. In this paper, a characterization is given for block graphs having a unique minimum dominating set. With this result, we generalize a theorem of Gunther, Hartnell, Markus and Rall for trees.     

Degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle

Let 1a<b be integers and G a Hamiltonian graph of order |G|(a+b)(2a+b)/b. Suppose that δ(G)a+2 and max{deg_G(x), deg_G(y)}a|G|/(a+b)+2 for each pair of nonadjacent vertices x and y in G. Then G has an [a,b]-factor which is edge-disjoint from a given Hamiltonian cycle. The lower bound on the degree condition is sharp. For the case of odd a=b, there exists a graph satisfying the conditions of the theorem but having no desired factor. As consequences, we have the degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle.     

Graphs whose acyclic graphoidal covering number is one less than its maximum degree

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. In this paper we characterize the class of graphs G for which η_a=Δ−1 where Δ is the maximum degree of a vertex in G.     

Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D)=∑_vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑_vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that

for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.     

Some results on characterizing the edges of connected graphs with a given domination number

A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m₁ (G, D) denote the number of edges that have neither endpoint in D, and let m₂ (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m₁ (G, D), m₂ (G, D)) can attain for connected graphs having a given domination number.     

Strong equality of domination parameters in trees

We study the concept of strong equality of domination parameters. Let P₁ and P₂ be properties of vertex subsets of a graph, and assume that every subset of V(G) with property P₂ also has property P₁. Let ψ₁(G) and ψ₂(G), respectively, denote the minimum cardinalities of sets with properties P₁ and P₂, respectively. Then ψ₁(G)ψ₂(G). If ψ₁(G)=ψ₂(G) and every ψ₁(G)-set is also a ψ₂(G)-set, then we say ψ₁(G) strongly equals ψ₂(G), written ψ₁(G)≡ψ₂(G). We provide a constructive characterization of the trees T such that γ(T)≡i(T), where γ(T) and i(T) are the domination and independent domination numbers, respectively. A constructive characterization of the trees T for which γ(T)=γ_t(T), where γ_t(T) denotes the total domination number of T, is also presented.     

k-Subdomination in graphs

For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f : V→{−1,1} such that ∑_uNG[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ_ks(G), is the minimum of ∑_vVf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ_ks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ_ks(G), the signed domination number γ_s(G) and the majority domination number γ_maj(G).     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

Eigenvalues of the Laplacian of a graph

Let G be a finite undirected graph with no loops or multiple edges. We define the Laplacian matrix of G,Δ(G)by Δ_ij= degree of vertex i and Δ_ij-1 if there is an edge between vertex i and vertex j. In this paper we relate the structure of the graph G to the eigenvalues of A(G): in particular we prove that all the eigenvalues of Δ(G) are non-negative, less than or equal to the number of vertices, and less than or equal to twice the maximum vertex degree. Precise conditions for equality are given.     

Choosability of planar graphs

A graph G = G(V, E) with lists L(v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L(v). We say G is k-choosable if there is at least one L-list colouring for every possible list assignment L with L(v) = k v V(G).

Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”.     

The extreme set condition of a graph

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by ν(G). Define the deficiency of G, def(G), by the equation def(G)=|V(G)|−2ν(G). A set of points X in G is called an extreme set if def(G−X)=def(G)+|X|. Let c₀(G) denote the number of the odd components of G. A set of points X in G is called a barrier if c₀(G−X)=def(G)+|X|. In this paper, we obtain the following:

(1) Let G be a simple graph containing an independent set of size i, where i2. If X is extreme in G for every independent set X of size i in G, then there exists a perfect matching in G.

(2) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is extreme in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|i, and |Γ(Y)||U|−i+m+1 for any Y U, |Y|=m (1mi−1).

(3) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is a barrier in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|=i, and |Γ(Y)|m+1 for any Y U, |Y|=m (1mi−1).     

Harary's conjectures on integral sum graphs

Let N denote the set of positive integers and Z denote all integers. The (integral) sum graph of a finite subset S N(Z) is the graph (S, E) with uv ε E if and only if u + v ε S. A graph G is said to be an (integral) sum graph if it is isomorphic to the (integral) sum graph of some S N(Z). The (integral) sum number of a given graph G is the smallest number of isolated nodes which when added to G result in an (integral) sum graph.

We show that the integral sum number of a complete graph with n 4 nodes equals 2n − 3, which proves a conjecture of Harary. And we disprove another conjecture of Harary by showing that there are infinitely many trees which are not caterpillars but are integral sum graphs.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.