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.     

Nordhaus-Gaddum results for the convex domination number of a graph

The distance d _G (u, v) between two vertices u and v in a connected graph G is the length of the shortest uv-path in G. A uv-path of length d _G (u, v) is called a uv-geodesic. A set X is convex in G if vertices from all ab-geodesics belong to X for any two vertices a, b ?? X. The convex domination number ??_con(G) of a graph G equals the minimum cardinality of a convex dominating set. In the paper, Nordhaus-Gaddum-type results for the convex domination number are studied.     

The connectivity of a graph and its complement

Let G be a graph with minimum degree δ(G), edge-connectivity λ(G), vertex-connectivity κ(G), and let be the complement of G.In this article we prove that either λ(G)=δ(G) or . In addition, we present the Nordhaus-Gaddum type result . A family of examples will show that this inequality is best possible.     

Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers

For a graph G on n vertices with chromatic number χ(G), the Nordhaus-Gaddum inequalities state that , and . Much analysis has been done to derive similar inequalities for other graph parameters, all of which are integer-valued. We determine here the optimal Nordhaus-Gaddum inequalities for the circular chromatic number and the fractional chromatic number, the first examples of Nordhaus-Gaddum inequalities where the graph parameters are rational-valued.     

The product of the restrained domination numbers of a graph and its complement

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.In this paper,we show that if G is a graph of order n≥4,then γr(G)γr(G)≤2n.We also characterize the graphs achieving the upper bound.     

Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs

Let G=(V,E) be a graph. A set S⊆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. 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 total restrained domination number of G (restrained domination number of G, respectively), denoted by γ_tr(G) (γ_r(G), respectively), is the smallest cardinality of a total restrained dominating set (restrained dominating set, respectively) of G. We bound the sum of the total restrained domination numbers of a graph and its complement, and provide characterizations of the extremal graphs achieving these bounds. It is known (see [G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69.]) that if G is a graph of order n?2 such that both G and are not isomorphic to P₃, then . We also provide characterizations of the extremal graphs G of order n achieving these bounds.     

Inequality of Nordhaus-Gaddum type for total outer-connected domination in graphs

A set S of vertices in a graph G = (V, E) without isolated vertices is a total outer-connected dominating set (TCDS) of G if S is a total dominating set of G and G[V − S] is connected. The total outer-connected domination number of G, denoted by γ _tc (G), is the minimum cardinality of a TCDS of G. For an arbitrary graph without isolated vertices, we obtain the upper and lower bounds on γ _tc (G) + γ _tc ($ \bar G $ \bar G ), and characterize the extremal graphs achieving these bounds.     

Bounds on the number of isolates in sum graph labeling

A simple undirected graph H is called a sum graph if there is a labeling L of the vertices of H into distinct positive integers such that any two vertices u and v of H are adjacent if and only if there is a vertex w with label L(w)=L(u)+L(v). The sum number σ(G) of a graph G=(V,E) is the least integer r such that the graph H consisting of G and r isolated vertices is a sum graph. It is clear that σ(G)|E|. In this paper, we discuss general upper and lower bounds on the sum number. In particular, we prove that, over all graphs G=(V,E) with fixed |V|3 and |E|, the average of σ(G) is at least

Full-size image

. In other words, for most graphs, σ(G)Ω(|E|).     

The minimum number of subgraphs in a graph and its complement

For a graphb F without isolated vertices, let M(F; n) denote the minimum number of monochromatic copies of F in any 2-coloring of the edges of K_n. Burr and Rosta conjectured that when F has order t, size u, and a automorphisms. Independently, Sidorenko and Thomason have shown that the conjecture is false. We give families of graphs F of order t, of size u, and with a automorphisms where . We show also that the asymptotic value of M(F; n) is not solely a function of the order, size and number of automorphisms of F. © 1929 John Wiley & Sons, Inc.     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

On the Roman domination number of a graph

A Roman dominating function of a graph G is a labeling f:V(G)?{0,1,2} such that every vertex with label 0 has a neighbor with label 2. The Roman domination number γ_R(G) of G is the minimum of ∑_v∈V(G)f(v) over such functions. A Roman dominating function of G of weight γ_R(G) is called a γ_R(G)-function. A Roman dominating function f:V?{0,1,2} can be represented by the ordered partition (V₀,V₁,V₂) of V, where V_i={v∈V∣f(v)=i}. Cockayne et al. [E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004) 11-22] posed the following question: What can we say about the minimum and maximum values of |V₀|,|V₁|,|V₂| for a γ_R-function f=(V₀,V₁,V₂) of a graph G? In this paper we first show that for any connected graph G of order n≥3, , where γ(G) is the domination number of G. Also we prove that for any γ_R-function f=(V₀,V₁,V₂) of a connected graph G of order n≥3, , and .     

An upper bound for the path number of a graph

The path number of a graph G, denoted p(G), is the minimum number of edge-disjoint paths covering the edges of G. Lovász has proved that if G has u odd vertices and g even vertices, then p(G) ≤ 1/2 u + g - 1 ≤ n - 1, where n is the total number of vertices of G. This paper clears up an error in Lovász's proof of the above result and uses an extension of his construction to show that p(G) ≤ 1/2 u + [3/4g] ≤ [3/4n].     

The upper connected geodetic number and forcing connected geodetic number of a graph

For a connected graph G of order p≥2, a set S⊆V(G) is a geodetic set of G if each vertex v∈V(G) lies on an x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A connected geodetic set of G is a geodetic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected geodetic set of G is the connected geodetic number of G and is denoted by g_c(G). A connected geodetic set of cardinality g_c(G) is called a g_c-set of G. A connected geodetic set S in a connected graph G is called a minimal connected geodetic set if no proper subset of S is a connected geodetic set of G. The upper connected geodetic number is the maximum cardinality of a minimal connected geodetic set of G. We determine bounds for and determine the same for some special classes of graphs. For positive integers r,d and n≥d+1 with r≤d≤2r, there exists a connected graph G with , and . Also, for any positive integers 2≤a<b≤c, there exists a connected graph G such that g(G)=a, g_c(G)=b and . A subset T of a g_c-set S is called a forcing subset for S if S is the unique g_c-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected geodetic number of S, denoted by f_c(S), is the cardinality of a minimum forcing subset of S. The forcing connected geodetic number of G, denoted by f_c(G), is f_c(G)=min{f_c(S)}, where the minimum is taken over all g_c-sets S in G. It is shown that for every pair a,b of integers with 0≤a≤b−4, there exists a connected graph G such that f_c(G)=a and g_c(G)=b.     

On the doubly connected domination number of a graph

For a given connected graph G = (V, E), a set is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.     

Total domination and total domination subdivision number of a graph and its complement

A set S of vertices of a graph G=(V,E) with no isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγ_t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision numbersd_γt(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n?4, minimum degree δ and maximum degree Δ. We prove that if each component of G and has order at least 3 and , then and if each component of G and has order at least 2 and at least one component of G and has order at least 3, then . We also give a result on stronger than a conjecture by Harary and Haynes.