On the 2-rainbow domination in graphs

The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K₂. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k) this number is between ⌈4n/5⌉ and n with both bounds being sharp.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

Unprovability threshold for the planar graph minor theorem

This note is part of the implementation of a programme in foundations of mathematics to find exact threshold versions of all mathematical unprovability results known so far, a programme initiated by Weiermann. Here we find the exact versions of unprovability of the finite graph minor theorem with growth rate condition restricted to planar graphs, connected planar graphs and graphs embeddable into a given surface, assuming an unproved conjecture (*): ‘there is a number a>0 such that for all k≥3, and all n≥1, the proportion of connected graphs among unlabelled planar graphs of size n omitting the k-element circle as minor is greater than a’. Let γ be the unlabelled planar growth constant (27.2269≤γ<30.061). Let P(c) be the following first-order arithmetical statement with real parameter c: “for every K there is N such that whenever G₁,G₂,…,G_N are unlabelled planar graphs with |G_i|<K+c⋅log₂i then for some i<j≤N, G_i is isomorphic to a minor of G_j”. Then

1.

for every , P(c) is provable in IΔ₀+exp;

2.

for every , P(c) is unprovable in .

We also give proofs of some upper and lower bounds for unprovability thresholds in the general case of the finite graph minor theorem.     

Independence and coloring properties of direct products of some vertex-transitive graphs

Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}.     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

An efficient condition for a graph to be Hamiltonian

Let G=(V,E) be a 2-connected simple graph and let d_G(u,v) denote the distance between two vertices u,v in G. In this paper, it is proved: if the inequality d_G(u)+d_G(v)?|V(G)|-1 holds for each pair of vertices u and v with d_G(u,v)=2, then G is Hamiltonian, unless G belongs to an exceptional class of graphs. The latter class is described in this paper. Our result implies the theorem of Ore [Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55]. However, it is not included in the theorem of Fan [New sufficient conditions for cycles in graph, J. Combin. Theory Ser. B 37 (1984) 221-227].     

On minimally circular-imperfect graphs

A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that ω_c(G-x)>ω(G-x) for some x∈V(G), then G=K_(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.     

On the null-spaces of acyclic and unicyclic singular graphs

For acyclic and unicyclic graphs we determine a necessary and sufficient condition for a graph G to be singular. Further, it is shown that this characterization can be used to construct a basis for the null-space of G.     

On the roots of independence polynomials of almost all very well-covered graphs

If s_k denotes the number of stable sets of cardinality k in graph G, and α(G) is the size of a maximum stable set, then is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97-106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187] if it has no isolated vertices, its order equals 2α(G) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98]. For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G^*. Under certain conditions, any well-covered graph equals G^* for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 44-68].The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197-210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles.In this paper we establish formulae connecting the coefficients of I(G;x) and I(G^*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G^*;x) different from -1, which appears as a root of multiplicity α(G^*)-α(G) for I(G^*;x). We also prove that the real roots of I(G^*;x) are in [-1,-1/2α(G^*)), while for a general graph of order n we show that its roots lie in |z|>1/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 84-87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders among well-covered trees.     

Altitude of regular graphs with girth at least five

The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.     

On graphs whose star sets are (co-)cliques

In this paper we study graphs all of whose star sets induce cliques or co-cliques. We show that the star sets of every tree for each eigenvalue are independent sets. Among other results it is shown that each star set of a connected graph G with three distinct eigenvalues induces a clique if and only if G=K_1,2 or K_2,…,2. It is also proved that stars are the only graphs with three distinct eigenvalues having a star partition with independent star sets.     

Mader’s Conjecture On Extremely Critical Graphs

A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K_2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.     

On choosability of some complete multipartite graphs and Ohba's conjecture

A graph G is said to be chromatic-choosable if ch(G)=χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. But for complete multipartite graphs, the graphs for which Ohba's conjecture has been verified are nothing more than K_{3*2,2*(k-3),1}, K_3,2*(k-1), and K_{s+3,2*(k-s-1),1*s}. These results have been obtained indirectly from the investigation about complete multipartite graphs by Gravier and Maffray and by Enomoto et al. In this paper we show that Ohba's conjecture is true for complete multipartite graphs K_{4,3,2*(k-4),1*2} and K_{5,3,2*(k-5),1*3}. By the way, we give some discussions about a result of Enomoto et al.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

On equality in an upper bound for the restrained and total domination numbers of a graph

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S and to a vertex in V?S. The restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of an RDS of G. A set S⊆V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γ_t(G), is the minimum cardinality of a TDS of G.Let δ and Δ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ?2, then it is shown that γ_r(G)?n-Δ, and we characterize the connected graphs with δ?2 achieving this bound that have no 3-cycle as well as those connected graphs with δ?2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211-219] showed that if G is a connected graph of order n?3 and Δ?n-2, then γ_t(G)?n-Δ. We further characterize the connected graphs G of order n?3 with Δ?n-2 that have no 3-cycle and achieve γ_t(G)=n-Δ.     

Tutte sets in graphs II: The complexity of finding maximum Tutte sets

A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs.     

Decomposition of 3-connected graphs

Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K _3,n for somen3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

Note on the 3-graph counting lemma

Szemerédi's regularity lemma proved to be a powerful tool in extremal graph theory. Many of its applications are based on the so-called counting lemma: if G is a k-partite graph with k-partition V₁∪?∪V_k, |V₁|=?=|V_k|=n, where all induced bipartite graphs G[V_i,V_j] are (d,ε)-regular, then the number of k-cliques K_k in G is . Frankl and Rödl extended Szemerédi's regularity lemma to 3-graphs and Nagle and Rödl established an accompanying 3-graph counting lemma analogous to the graph counting lemma above. In this paper, we provide a new proof of the 3-graph counting lemma.     

Graphs determined by their generalized characteristic polynomials

For a given graph G with (0, 1)-adjacency matrix A_G, the generalized characteristic polynomial of G is defined to be ?_G=?_G(λ,t)=det(λI-(A_G-tD_G)), where I is the identity matrix and D_G is the diagonal degree matrix of G. In this paper, we are mainly concerned with the problem of characterizing a given graph G by its generalized characteristic polynomial ?_G. We show that graphs with the same generalized characteristic polynomials have the same degree sequence, based on which, a unified approach is proposed to show that some families of graphs are characterized by ?_G. We also provide a method for constructing graphs with the same generalized characteristic polynomial, by using GM-switching.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.