Weakly connected domination stable trees

A dominating set D ⊆ V(G) is a weakly connected dominating set in G if the subgraph G[D] _w = (N _G [D], E _w ) weakly induced by D is connected, where E _w is the set of all edges having at least one vertex in D. Weakly connected domination number _γw (_G) of a graph G is the minimum cardinality among all weakly connected dominating sets in G. A graph G is said to be weakly connected domination stable or just _γw -stable if _γw (G) = _{γ w} (G + e) for every edge e belonging to the complement Ḡ of G. We provide a constructive characterization of weakly connected domination stable trees.      

Some Notes on Signed Edge Domination in Graphs

The closed neighborhood N_G[e] of an edge e in a graph G is the set consisting of e and of all edges having an end-vertex in common with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge dominating function of G. The signed edge domination number γ_s^′(G) of G is defined as . Recently, Xu proved that γ_s^′(G) ≥ |V(G)| − |E(G)| for all graphs G without isolated vertices. In this paper we first characterize all simple connected graphs G for which γ_s^′(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphs G with precisely k cycles and γ_s^′(G) = 1 − k, 2 − k. A. Khodkar: Research supported by a Faculty Research Grant, University of West Georgia. Send offprint requests to: Abdollah Khodkar.     

Paired Domination Vertex Critical Graphs

Let γ _pr (G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ _pr (G – v) < γ _pr (G). We call these graphs γ _pr -critical. In this paper, we present a method of constructing γ _pr -critical graphs from smaller ones. Moreover, we show that the diameter of a γ _pr -critical graph is at most and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear]. Xinmin Hou: Research supported by NNSF of China (No.10701068 and No.10671191).     

On signed distance-k-domination in graphs

The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N _k (v), is the set N _k (v) = {u: u ≠ v and d(u, v) ⩽ k}. N _k [v] = N _k (v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex . The signed distance-k-domination number, denoted by γ _k,s (G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ _2,s (G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ _2,s (T) is not bounded from below in general for any tree T.     

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.     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

Trees with Equal Domination and Restrained Domination Numbers

Let G = (V,E) be a graph and let S V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set S is a dominating set (DS) if every vertex in V − S is adjacent to a vertex in S. Further, if every vertex in V − S is also adjacent to a vertex in V − S, then S is a restrained dominating set (RDS). The domination number of G, denoted by γ(G), is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T)=γ_r(T); (ii) T is a γ-excellent tree and T ≠ K₂; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γ_r(T) ≤ (n + ℓ + 1)/2, and we characterize those trees achieving equality.     

Lower bounds on signed edge total domination numbers in graphs

The open neighborhood N _G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ _st ′(G). Obviously, γ _st ′(G) is defined only for graphs G which have no connected components isomorphic to K ₂. In this paper we present some lower bounds for γ _st ′(G). In particular, we prove that γ _st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ _st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.     

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 Restrained Domination in Cubic Graphs

A set S of vertices in a graph G = (V, E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. Let G be a cubic graph of order n. In this paper we establish an upper bound on γ _tr (G). If adding the restriction that G is claw-free, then we show that γ _tr (G) = γ _t (G) where γ _t (G) is the total domination number of G, and thus some results on total domination in claw-free cubic graphs are valid for total restrained domination. Research was partially supported by the NNSF of China (Nos. 60773078, 10832006), the ShuGuang Plan of Shanghai Education Development Foundation (No. 06SG42) and Shanghai Leading Academic Discipline Project (No. S30104).     

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.     

On hamiltonicity of <Emphasis Type="Italic">P</Emphasis><Subscript>3</Subscript>-dominated graphs

We introduce a new class of graphs which we call P ₃-dominated graphs. This class properly contains all quasi-claw-free graphs, and hence all claw-free graphs. Let G be a 2-connected P ₃-dominated graph. We prove that G is hamiltonian if α(G ²) ≤ κ(G), with two exceptions: K _2,3 and K _1,1,3. We also prove that G is hamiltonian, if G is 3-connected and |V(G)| ≤ 5δ(G) − 5. These results extend known results on (quasi-)claw-free graphs. This paper was completed when both authors visited the Center for Combinatorics, Nankai University, Tianjin. They gratefully acknowledge the hospitality and support of the Center for Combinatorics and Nankai University. The work of E.Vumar is sponsored by SRF for ROCS, REM.     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

An application of the Turán theorem to domination in graphs

A function f:V(G)→{+1,−1} defined on the vertices of a graph G is a signed dominating function if for any vertex v the sum of function values over its closed neighborhood is at least 1. The signed domination number γ_s(G) of G is the minimum weight of a signed dominating function on G. By simply changing “{+1,−1}” in the above definition to “{+1,0,−1}”, we can define the minus dominating function and the minus domination number of G. In this note, by applying the Turán theorem, we present sharp lower bounds on the signed domination number for a graph containing no (k+1)-cliques. As a result, we generalize a previous result due to Kang et al. on the minus domination number of k-partite graphs to graphs containing no (k+1)-cliques and characterize the extremal graphs.     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph 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. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

Matching properties in connected domination critical graphs

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].     

Graphic Sequences with a Realization Containing a Union of Cliques

An integer sequence π is said to be graphic if it is the degree sequence of some simple graph G. In this case we say that G is a realization of π. Given a graph H, and a graphic sequence π we say that π is potentially H-graphic if there is some realization of π that contains H as a subgraph. We define σ(H,n) to be the minimum even integer such that every graphic sequence with sum at least σ(H,n) is potentially H-graphic. In this paper, we determine σ(H,n) for the graph H = K_m1∪ K_m2∪...∪ K_mk when n is a sufficiently large integer. This is accomplished by determining σ(K_j + kK₂,n) where j and k are arbitrary positive integers, and considering the case where j = m − 2k and m = ∑ m_i.     

On <Emphasis Type="Italic">k</Emphasis>-pairable graphs from trees

The concept of the k-pairable graphs was introduced by Zhibo Chen (On k-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter p(G), called the pair length of a graph G, as the maximum k such that G is k-pairable and p(G) = 0 if G is not k-pairable for any positive integer k. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be trees. That is, we characterize the trees G with p(G) = 1 and prove that p(G □ H) = p(G) + p(H) when both G and H are trees.     

A Characterization of 3-(γ c , 2)-Critical Claw-Free Graphs Which are not 3-γ c -Critical

Let γ _c (G) denote the minimum cardinality of a connected dominating set for G. A graph G is k-γ _c -critical if γ _c (G) = k, but γ _c (G + xy) < k for ${xy \in E(\overline {G})}$ . Further, for integer r ≥ 2, G is said to be k-(γ _c , r)-critical if γ _c (G) = k, but γ _c (G + xy) < k for each pair of non-adjacent vertices x and y that are at distance at most r apart. k-γ _c -critical graphs are k-(γ _c , r)-critical but the converse need not be true. In this paper, we give a characterization of 3-(γ _c , 2)-critical claw-free graphs which are not 3-γ _c -critical. In fact, we show that there are exactly four classes of such graphs.     

Characterizing defect n-extendable graphs and -critical graphs

A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n(|V(G)|-2)/2, then G is said to be defect n-extendable. If deleting any k vertices in G where k|V(G)|-2, the remaining graph has a perfect matching, then G is a k-critical graph. This paper first shows that the connectivity of defect n-extendable graphs can be any integer. Then the characterizations of defect n-extendable graphs and (2k+1)-critical graphs using M-alternating paths are presented.