Domination versus disjunctive domination in graphs

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number of G is the minimum cardinality of a dominating set of G. For a positive integer b, a set S of vertices in a graph G is a b-disjunctive dominating set in G if every vertex v not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it in G. The b-disjunctive domination number of G is the minimum cardinality of a b-disjunctive dominating set. In this paper, we continue the study of disjunctive domination in graphs. We present properties of b-disjunctive dominating sets in a graph. A characterization of minimal b-disjunctive dominating sets is given. We obtain bounds on the ratio of the domination number and the b-disjunctive domination number for various families of graphs, including regular graphs and trees.     

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.     

Roman and Total Domination

Abstract

A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set is the total domination number ^γt(G). A Roman dominating function on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u with f (u)=0 is adjacent to at least one vertex v of G for which f (v)=2. The minimum of f (V (G))=∑_{u ∈ V (G)} f (u) over all such functions is called the Roman domination number γR (G). We show that γt(G) ≤ γR (G) with equality if and only if ^γt(G)=2γ(G), where γ(G) is the domination number of G. Moreover, we characterize the extremal graphs for some graph families.     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. 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 matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

Partitioning the Vertices of a Graph into Two Total Dominating Sets

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S. We study graphs whose vertex set can be partitioned into two total dominating sets. In particular, we develop several sufficient conditions for a graph to have a vertex partition into two total dominating sets. We also show that with the exception of the cycle on five vertices, every selfcomplementary graph with minimum degree at least two has such a partition.     

Packing in regular graphs

A set S of vertices in a graph G is a packing if the vertices in S are pairwise at distance at least 3 apart in G. The packing number of G, denoted by ρ(G), is the maximum cardinality of a packing in G. Favaron [Discrete Math. 158 (1996), 287–293] showed that if G is a connected cubic graph of order n different from the Petersen graph, then ρ(G) ≥ n/8. In this paper, we generalize Favaron’s result. We show that for k ≥ 3, if G is a connected k-regular graph of order n that is not a diameter-2 Moore graph, then ρ(G) ≥ n/(k² ? 1).     

ON A CONJECTURE ON nTH ORDER DEGREE REGULAR GRAPHS

Abstract

For n a positive integer and v a vertex of a graph G, the nth order degree of v in G, denoted by deg_nv, is the number of vertices at distance n from v. The graph G is said to be nth order regular of degree k if, for every vertex v of G, deg_nv = k. The following conjecture due to Alavi, Lick, and Zou is proved: For n ≥ 2, if G is a connected nth order regular graph of degree 1, then G is either a path of length 2n—1 or G has diameter n. Properties of nth order regular graphs of degree k, k ≥ 1, are investigated.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Coverings of the Vertices of a Graph by Small Cycles

Given a graph G with n vertices, we call c_k(G) the minimum number of elementary cycles of length at most k necessary to cover the vertices of G. We bound c_k(G) from the minimum degree and the order of the graph.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

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     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

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-Δ.     

A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

Bounds on a generalized domination parameter

Abstract

If n is an integer, n ≥ 2 and u and v are vertices of a graph G, then u and v are said to be K_n-adjacent vertices of G if there is a subgraph of G, isomorphic to K_n , containing u and v. For n ≥ 2, a K_n- dominating set of G is a set D of vertices such that every vertex of G belongs to D or is K_n-adjacent to a vertex of D. The K_n-domination number γK_n (G) of G is the minimum cardinality among the K_n-dominating sets of vertices of G. It is shown that, for n ε {3,4}, if G is a graph of order p with no K_n-isolated vertex, then γK_n (G) ≤ p/n. We establish that this is a best possible upper bound. It is shown that the result is not true for n ≥ 5.     

Total restrained domination in graphs with minimum degree two

In this paper, we continue the study of total restrained domination in graphs, a concept introduced by Telle and Proskurowksi (Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550) as a vertex partitioning problem. A set S of vertices in a graph G=(V,E) is a total restrained dominating set of G 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 minimum cardinality of a total restrained dominating set of G is the total restrained domination number of G, denoted by γ_tr(G). Let G be a connected graph of order n with minimum degree at least 2 and with maximum degree Δ where Δ?n-2. We prove that if n?4, then and this bound is sharp. If we restrict G to a bipartite graph with Δ?3, then we improve this bound by showing that and that this bound is sharp.     

Bounds on cost effective domination numbers

A vertex υ in a set S is said to be cost effective if it is adjacent to at least as many vertices in V\S as it is in S and is very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is (very) cost effective if every vertex in S is (very) cost effective. The minimum cardinality of a (very) cost effective dominating set of G is the (very) cost effective domination number of G. Our main results include a quadratic upper bound on the very cost effective domination number of a graph in terms of its domination number. The proof of this result gives a linear upper bound for hereditarily sparse graphs which include trees. We show that no such linear bound exists for graphs in general, even when restricted to bipartite graphs. Further, we characterize the extremal trees attaining the bound. Noting that the very cost effective domination number is bounded below by the domination number, we show that every value of the very cost effective domination number between these lower and upper bounds for trees is realizable. Similar results are given for the cost effective domination number.     

Matching behaviour is asymptotically normal

Ak-matching in a graphG is a set ofk edges, no two of which have a vertex in common. The number of these inG is writtenp(G, k). Using an idea due to L. H. Harper, we establish a condition under which these numbers are approximately normally distributed. We show that our condition is satisfied ifn=|V(G)| is large compared to the maximum degree Δ of a vertex inG(i.e. Δ=o(n)) orG is a large complete graph. One corollary of these results is that the number of points fixed by a randomly chosen involution in the symmetric groupS is asymptotically normally distributed.     

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.