Inequalities of Nordhaus-Gaddum type for doubly connected domination number

A set S of vertices of a connected graph G is a doubly connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and V−S are connected. The doubly connected domination numberγ_cc(G) is the minimum size of such a set. We prove that when G and are both connected of order n, and we describe the two infinite families of extremal graphs achieving the bound.     

Bounds relating the weakly connected domination number to the total domination number and the matching number

Let G=(V,E) be a connected graph. A dominating set S of G is a weakly connected dominating set of G if the subgraph (V,E∩(S×V)) of G with vertex set V that consists of all edges of G incident with at least one vertex of S is connected. The minimum cardinality of a weakly connected dominating set of G is the weakly connected domination number, denoted . A set S of vertices in 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. In this paper, we show that . Properties of connected graphs that achieve equality in these bounds are presented. We characterize bipartite graphs as well as the family of graphs of large girth that achieve equality in the lower bound, and we characterize the trees achieving equality in the upper bound. The number of edges in a maximum matching of G is called the matching number of G, denoted α^′(G). We also establish that , and show that for every tree T.     

The forcing hull and forcing geodetic numbers of graphs

For every pair of vertices u,v in a graph, a u-v geodesic is a shortest path from u to v. For a graph G, let I_G[u,v] denote the set of all vertices lying on a u-v geodesic. Let S⊆V(G) and I_G[S] denote the union of all I_G[u,v] for all u,v∈S. A subset S⊆V(G) is a convex set of G if I_G[S]=S. A convex hull [S]_G of S is a minimum convex set containing S. A subset S of V(G) is a hull set of G if [S]_G=V(G). The hull number h(G) of a graph G is the minimum cardinality of a hull set in G. A subset S of V(G) is a geodetic set if I_G[S]=V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset F⊆V(G) is called a forcing hull (or geodetic) subset of G if there exists a unique minimum hull (or geodetic) set containing F. The cardinality of a minimum forcing hull subset in G is called the forcing hull number f_h(G) of G and the cardinality of a minimum forcing geodetic subset in G is called the forcing geodetic number f_g(G) of G. In the paper, we construct some 2-connected graph G with (f_h(G),f_g(G))=(0,0),(1,0), or (0,1), and prove that, for any nonnegative integers a, b, and c with a+b≥2, there exists a 2-connected graph G with (f_h(G),f_g(G),h(G),g(G))=(a,b,a+b+c,a+2b+c) or (a,2a+b,a+b+c,2a+2b+c). These results confirm a conjecture of Chartrand and Zhang proposed in [G. Chartrand, P. Zhang, The forcing hull number of a graph, J. Combin. Math. Combin. Comput. 36 (2001) 81-94].     

An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ_r(G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then .     

On hamiltonian colorings for some graphs

For a connected graph G and any two vertices u and v in G, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices u and v in G. The value of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number of G is taken over all hamiltonian colorings c of G. In this paper we discuss the hamiltonian chromatic number of graphs G with . As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars.     

The exact domination number of the generalized Petersen graphs

Let G=(V,E) be a graph. A subset S⊆V is a dominating set of G, if every vertex u∈V−S is dominated by some vertex v∈S. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. For the generalized Petersen graph G(n), Behzad et al. [A. Behzad, M. Behzad, C.E. Praeger, On the domination number of the generalized Petersen graphs, Discrete Mathematics 308 (2008) 603-610] proved that and conjectured that the upper bound is the exact domination number. In this paper we prove this conjecture.     

Circular game chromatic number of graphs

In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χ_cg(G) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χ_cg(G)≤2χ_a(G)(χ_a(G)+1), where χ_a(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles.     

Fast algorithms for identifying maximal common connected sets of interval graphs

Given a family of interval graphs F={G₁=(V,E₁),…,G_k=(V,E_k)} on the same vertices V, a set S⊂V is a maximal common connected set of F if the subgraphs of G_i,1?i?k, induced by S are connected in all G_i and S is maximal for the inclusion order. The maximal general common connected set for interval graphs problem (gen-CCPI) consists in efficiently computing the partition of V in maximal common connected sets of F. This problem has many practical applications, notably in computational biology. Let n=|V| and . For k?2, an algorithm in O((kn+m)logn) time is presented in Habib et al. [Maximal common connected sets of interval graphs, in: Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 3109, Springer, Berlin, 2004, pp. 359-372]. In this paper, we improve this bound to O(knlogn+m). Moreover, if the interval graphs are given as k sets of n intervals, which is often the case in bioinformatics, we present a simple time algorithm.     

Minimally 3-restricted edge connected graphs

For a connected graph G=(V,E), an edge set S⊂E is a 3-restricted edge cut if G−S is disconnected and every component of G−S has order at least three. The cardinality of a minimum 3-restricted edge cut of G is the 3-restricted edge connectivity of G, denoted by λ₃(G). A graph G is called minimally 3-restricted edge connected if λ₃(G−e)<λ₃(G) for each edge e∈E. A graph G is λ₃-optimal if λ₃(G)=ξ₃(G), where , ω(U) is the number of edges between U and V?U, and G[U] is the subgraph of G induced by vertex set U. We show in this paper that a minimally 3-restricted edge connected graph is always λ₃-optimal except the 3-cube.     

On global domination critical graphs

A dominating set of a graph G=(V,E) is a subset S⊆V such that every vertex not in S is adjacent to at least one vertex of S. The domination number of G is the cardinality of a smallest dominating set. The global domination number, γ_g(G), is the cardinality of a smallest set S that is simultaneously a dominating set of both G and its complement . Graphs for which γ_g(G−e)>γ_g(G) for all edges e∈E are characterized, as are graphs for which γ_g(G−e)<γ_g(G) for all edges e∈E whenever is disconnected. Progress is reported in the latter case when is connected.     

On pitfalls in computing the geodetic number of a graph

Given a simple connected graph G = (V, E) the geodetic closure of a subset S of V is the union of all sets of nodes lying on some geodesic (or shortest path) joining a pair of nodes . The geodetic number, denoted by g(G), is the smallest cardinality of a node set S ^* such that I[S ^*] = V. In “The geodetic number of a graph”, [Harary et al. in Math. Comput. Model. 17:89–95, 1993] propose an incorrect algorithm to find the geodetic number of a graph G. We provide counterexamples and show why the proposed approach must fail. We then develop a 0–1 integer programming model to find the geodetic number. Computational results are given.     

Packing directed cycles efficiently

Let G be a simple digraph. The dicycle packing number of G, denoted ν_c(G), is the maximum size of a set of arc-disjoint directed cycles in G. Let G be a digraph with a nonnegative arc-weight function w. A function ψ from the set C of directed cycles in G to R₊ is a fractional dicycle packing of G if ∑_e∈C∈Cψ(C)?w(e) for each e∈E(G). The fractional dicycle packing number, denoted , is the maximum value of ∑_C∈Cψ(C) taken over all fractional dicycle packings ψ. In case w≡1 we denote the latter parameter by .Our main result is that where n=|V(G)|. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least ν_c(G)-o(n²) in randomized polynomial time. Since computing ν_c(G) is an NP-Hard problem, and since almost all digraphs have ν_c(G)=Θ(n²) our result is a FPTAS for computing ν_c(G) for almost all digraphs.The result uses as its main lemma a much more general result. Let F be any fixed family of oriented graphs. For an oriented graph G, let ν_F(G) denote the maximum number of arc-disjoint copies of elements of F that can be found in G, and let denote the fractional relaxation. Then, . This lemma uses the recently discovered directed regularity lemma as its main tool.It is well known that can be computed in polynomial time by considering the dual problem. We present a polynomial algorithm that finds an optimal fractional dicycle packing. Our algorithm consists of a solution to a simple linear program and some minor modifications, and avoids using the ellipsoid method. In fact, the algorithm shows that a maximum fractional dicycle packing with at most O(n²) dicycles receiving nonzero weight can be found in polynomial time.     

Domination subdivision numbers of trees

A set S of vertices of a graph G=(V,E) is a dominating set if every vertex of V(G)?S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number  is the minimum number of edges that must be subdivided in order to increase the domination number. Velammal showed that for any tree T of order at least 3, . In this paper, we give two characterizations of trees whose domination subdivision number is 3 and a linear algorithm for recognizing them.