A Characterization of Graphs with Equal Domination Number and Vertex Cover Number
Yunjian Wu
1∗and Qinglin Yu
2†1 Department of Mathematics
Southeast University, Nanjing 211189, China
2 Department of Mathematics and Statistics Thompson Rivers University, Kamloops, BC, Canada
Abstract
Let𝛾(𝐺) and𝛽(𝐺) denote the domination number and the vertex cover num- ber of a graph𝐺, respectively. We use𝒢𝛾=𝛽for the set of graphs which have equal domination number and vertex cover number. In this short note, we present a characterization for the class𝒢𝛾=𝛽.
Key words: domination number, vertex cover number, matching number
1 Introduction
In this note, we consider simple finite graphs𝐺= (𝑉, 𝐸) only and follow [1] and [5] for terminology and definitions.
For 𝑆 ⊂ 𝑉(𝐺), ⟨𝑆⟩𝐺 denotes the subgraph induced by vertex set 𝑆, and 𝐺−𝑆 is the subgraph of𝐺obtained by deleting the vertices in𝑆and all the edges incident with them. A subset 𝑆 of 𝑉(𝐺) is a dominating set if every vertex of 𝐺 is either in 𝑆 or is adjacent to a vertex in 𝑆. The minimum cardinality of a dominating set is called the domination number and denoted by 𝛾(𝐺). A set 𝐷 ⊆𝑉(𝐺) is a vertex cover if every edge of 𝐺 has at least one end in 𝐷. The vertex cover number 𝛽(𝐺) is the minimum cardinality of a vertex cover of 𝐺.
The class of graphs with equal domination and vertex cover number is simplify denoted by 𝒢𝛾=𝛽. A characterization of the family 𝒢𝛾=𝛽 with minimum degree one
∗Corresponding author: [email protected]
†The work is supported by Natural Sciences and Engineering Research Council of Canada.
was given in [5] but was incomplete. The graph 𝐺 shown in Figure 1 has domination number 4 and vertex cover number 5, respectively. However, the graph𝐺was included in the characterization in [5]. Independently, Hartnell and Rall [2] also gave a charac- terization, but their characterization was involved and complicated. In this note, we give a new clear characterization of graphs in 𝒢𝛾=𝛽 with minimum degree one.
Figure 1: 𝛾(𝐺) = 4 and 𝛽(𝐺) = 5
The minimum degree of𝐺is denoted by𝛿(𝐺). We denote by𝐼(𝐺) the set of isolated vertices of 𝐺, and by𝐸𝑛𝑑(𝐺) the set of end-vertices (i.e., vertices of degree one) of 𝐺.
An edge incident with an end-vertex is called a pendantedge. A vertex adjacent to an end-vertex is called astem, and 𝑆𝑡𝑒𝑚(𝐺) denotes the set of stems of 𝐺.
A graph with a single vertex is called a trivial graph. The corona 𝐻 ∘𝐾1 of a graph 𝐻 is the graph obtained from 𝐻 by adding a pendant edge to each vertex of 𝐻. A connected graph 𝐺 of order at least three is called a generalized corona if 𝑉(𝐺) =𝐸𝑛𝑑(𝐺)∪𝑆𝑡𝑒𝑚(𝐺).
For a graph 𝐺, the maximum size of a matching is called the matching number of 𝐺 and denoted by 𝜈(𝐺). The class of extremal graphs with equal domination and matching number, for abbreviation, denoted by 𝒢𝛾=𝜈.
The following result is well-known.
Theorem 1. (see [3]) If 𝐺 is a graph without isolated vertices, then 𝛾(𝐺) ≤ 𝜈(𝐺) ≤ 𝛽(𝐺).
There is a characterization of the family 𝒢𝛾=𝜈 in [6]. Unfortunately, their charac- terization is incomplete, so it was corrected in [4] as follows.
Theorem 2 (Kano, Wu and Yu [4]). Let 𝐺 be a connected graph with𝛿(𝐺) = 1. Then 𝐺 ∈ 𝒢𝛾=𝜈 if and only if 𝐺 is 𝐾2 or a generalized corona, or every component 𝐻 of 𝐺−(𝐸𝑛𝑑(𝐺)∪𝑆𝑡𝑒𝑚(𝐺)) is one of the following:
(𝑖) 𝐻 is a trivial graph;
(𝑖𝑖) 𝐻 is a connected bipartite graph with bipartition 𝑋 and 𝑌, where 1 ≤ ∣𝑋∣ < ∣𝑌∣. Let 𝑈 = 𝑉(𝐻)∩ 𝑁𝐺(𝑆𝑡𝑒𝑚(𝐺)). Then ∅ ∕= 𝑈 ⊆ 𝑌
and for any two distinct vertices 𝑥1, 𝑥2 of 𝑋 that are adjacent to a com- mon vertex of 𝑌, there exist two distinct vertices 𝑦1 and 𝑦2 in 𝑌 −𝑈 such that 𝑁𝐻(𝑦𝑖) = {𝑥1, 𝑥2}, for 𝑖= 1,2;
(𝑖𝑖𝑖)𝐻 is isomorphic to one of graphs shown in Figure 2, and 𝛾(𝐻−𝑋) = 𝛾(𝐻) for all ∅ ∕=𝑋 ⊆𝑈 ⊂𝑉(𝐻), where 𝑈 =𝑉(𝐻)∩𝑁𝐺(𝑆𝑡𝑒𝑚(𝐺)).
@@ r
r
r r
r @
@ r
r
r r
r @
@ r
r
r r
r @
@ r
r r
Figure 2: Graphs in (𝑖𝑖𝑖) of Theorem 2.
It is clear that 𝒢𝛾=𝛽 is a subclass of 𝒢𝛾=𝜈 from Theorem 1. Next we use Theorem 2 to give a complete characterization of graphs 𝐺 with 𝛿(𝐺) = 1 in the family𝒢𝛾=𝛽.
2 Main results
We start with two lemmas, then give a clear characterization of graphs in 𝒢𝛾=𝛽 with minimum degree one.
Lemma 1 (Randerath and Volkmann [5]). Let 𝐺 be a connected graph with 𝛿(𝐺)≥2.
Then 𝛾(𝐺) =𝛽(𝐺) if and only if 𝐺 is a bipartite graph with bipartition 𝑋 and 𝑌 and the following property is satisfied: for any two distinct vertices 𝑥1, 𝑥2 of 𝑋 that are adjacent to a common vertex of 𝑌, there exist two distinct vertices 𝑦1 and 𝑦2 in 𝑌 such that 𝑁𝐺(𝑦𝑖) ={𝑥1, 𝑥2} for 𝑖= 1,2. Moreover, 𝛾(𝐺) = 𝛽(𝐺) =∣𝑋∣.
Lemma 2 (Volkmann [7]). Let 𝐺 be a connected graph and𝐻 be a spanning subgraph of 𝐺 without isolated vertices. If 𝛾(𝐺) = 𝛽(𝐺), then 𝐻 ∈ 𝒢𝛾=𝛽 and 𝛾(𝐻) = 𝛾(𝐺) = 𝛽(𝐺) =𝛽(𝐻). In particular, each component of 𝐻 is in 𝒢𝛾=𝛽.
Now we give a complete characterization of graphs in 𝒢𝛾=𝛽 with 𝛿(𝐺) = 1.
Theorem 3. Let𝐺be a connected graph with 𝛿(𝐺) = 1. Then𝛾(𝐺) = 𝛽(𝐺)if and only if𝐺is𝐾2or a generalized corona, or for each component𝐻 of𝐺−(𝐸𝑛𝑑(𝐺)∪𝑆𝑡𝑒𝑚(𝐺)), it satisfies one of the following:
(𝑖) 𝐻 is a trivial graph;
(𝑖𝑖) 𝐻 is a connected bipartite graph with bipartition 𝑋 and 𝑌, where 1≤
∣𝑋∣ < ∣𝑌∣. Let 𝑈𝐻 = 𝑉(𝐻)∩ 𝑁𝐺(𝑆𝑡𝑒𝑚(𝐺)). Then ∅ ∕= 𝑈𝐻 ⊆ 𝑌 and for any two distinct vertices 𝑥1, 𝑥2 of 𝑋 that are adjacent to a common vertex of 𝑌, there exist two distinct vertices 𝑦1 and𝑦2 in 𝑌 −𝑈𝐻 such that 𝑁𝐻(𝑦𝑖) ={𝑥1, 𝑥2}, for 𝑖= 1,2.
Proof. If𝐺 is 𝐾2 or a generalized corona, then 𝛾(𝐺) =𝛽(𝐺) and the theorem holds.
So, in the following, we may assume that𝐺is neither𝐾2 nor a generalized corona, and 𝐺 has order at least three. We first show the sufficiency. Without loss of generality, assume there is a minimum vertex cover set containing all the vertices in𝑆𝑡𝑒𝑚(𝐺). So
𝛽(𝐺) =∣𝑆𝑡𝑒𝑚(𝐺)∣+∑
𝐻
𝛽(𝐻), (1)
where 𝐻 runs over all non-trivial components of 𝐺−(𝐸𝑛𝑑(𝐺)∪𝑆𝑡𝑒𝑚(𝐺)).
Let 𝐺˜ be a graph consisting of all the non-trivial component 𝐻 of 𝐺−(𝐸𝑛𝑑(𝐺)∪ 𝑆𝑡𝑒𝑚(𝐺)) and the subgraph〈
𝐸𝑛𝑑(𝐺) ∪ 𝑆𝑡𝑒𝑚(𝐺) ∪ 𝐼(𝐺−(𝐸𝑛𝑑(𝐺)∪𝑆𝑡𝑒𝑚(𝐺)))〉
𝐺. Then𝐺˜is a spanning subgraph of 𝐺without isolated vertices. So 𝛾(𝐻) =𝛽(𝐻) =∣𝑋∣
by Lemma 1 and Lemma 2.
Without loss of generality, for every minimum dominating set 𝐿 of order 𝛾(𝐺) in 𝐺, we assume 𝑆𝑡𝑒𝑚(𝐺) ⊆ 𝐿. Let 𝐻 be a non-trivial component of 𝐺−(𝐸𝑛𝑑(𝐺)∪ 𝑆𝑡𝑒𝑚(𝐺)), and 𝑈𝐻 denote the set of vertices of𝐻 dominated by𝑆𝑡𝑒𝑚(𝐺), then all the vertices in 𝐻−𝑈𝐻 are dominated by 𝑉(𝐻)∩𝐿. By the assumption, 𝐻 is a bipartite graph with bipartition𝑋 and𝑌, where 1≤ ∣𝑋∣<∣𝑌∣. Since𝑈𝐻 ⊆𝑌, all the vertices in 𝑋 of𝐻 are of degree at least two. Let𝑈𝐻′ ⊆𝑈𝐻 and𝑈𝐻′′ =𝑈𝐻−𝑈𝐻′ . Suppose𝑈˜ ⊆𝑈𝐻′′
is the set of vertices of degree one in graph 𝐻−𝑈𝐻′ and 𝐻′ =⟨𝑉(𝐻)−𝑈𝐻′ ∪𝑈˜⟩𝐻, Claim 1. 𝐻′ is a trivial graph or all the vertices in 𝑋 of graph 𝐻′ are of degree at least two.
Let 𝑥 ∈ 𝑋 be an isolated vertex in graph 𝐻′, then 𝑥 is either adjacent to at least one vertex of degree at least two in𝐻 or all neighbors of 𝑥 in𝐻 are end-vertices. If it is the former case, then by assumption (𝑖𝑖), 𝑥 has at least two neighbors in 𝐻 −𝑈𝐻, which contradicts to that 𝑥 is an isolated vertex. Otherwise, 𝑈𝐻′ ∪𝑈˜ =𝑌 and 𝐻 is a star 𝐾1,𝑛 (𝑛≥ 2) since 𝐻 is connected. Hence if 𝑥 ∈𝑋 is an isolated vertex in graph 𝐻′ then 𝐻′ is a trivial graph. Next suppose 𝑥1 ∈𝑋 is a vertex of degree one in graph 𝐻′ and adjacent to a vertex𝑦∈𝑌 −𝑈𝐻′ ∪𝑈˜ in𝐻′. Since all the vertices of𝑌 −𝑈𝐻′ ∪𝑈˜ in 𝐻′ are of degree two, then𝑦 is adjacent to another vertex 𝑥2 in𝑋. By assumption (𝑖𝑖), there exist two distinct vertices 𝑦1 and𝑦2 in 𝑌 −𝑈𝐻 such that 𝑁𝐻(𝑦𝑖) ={𝑥1, 𝑥2}, for 𝑖= 1,2. A contradiction to 𝑑𝐻′(𝑣) = 1, i.e. 𝑑𝐻′(𝑣)≥2.
Claim 2. 𝛾(𝐻−𝑈𝐻′ ) =𝛾(𝐻), for all 𝑈𝐻′ ⊆𝑈𝐻.
If 𝐻′ is a trivial graph, then 𝐻 is a star𝐾1,𝑛 (𝑛≥2) by the proof of Claim 1. The claim holds. Otherwise, 𝐻′ is a connected bipartite graph with minimum degree at least two and satisfies the condition of Lemma 1. So𝛾(𝐻′) = ∣𝑋∣and𝑋 is a minimum dominating set of graph 𝐻′. Hence adding some pendant edges adjacent to vertices in 𝑋 will maintain the domination number, i.e., 𝛾(𝐻−𝑈𝐻′ ) = ∣𝑋∣=𝛾(𝐻).
Let 𝛾𝐻 = min{𝛾(𝐻−𝑈𝐻′ ) ∣ 𝑈𝐻′ ⊆𝑈𝐻}, then 𝛾𝐻 =𝛾(𝐻) by Claim 2. Now we can
compute 𝛾(𝐺) as follows:
𝛾(𝐺) = ∣𝐿∣=∣𝑆𝑡𝑒𝑚(𝐺)∣+∑
𝐻
𝛾𝐻
= ∣𝑆𝑡𝑒𝑚(𝐺)∣+∑
𝐻
𝛾(𝐻)
= ∣𝑆𝑡𝑒𝑚(𝐺)∣+∑
𝐻
𝛽(𝐻) =𝛽(𝐺). (by (1)) where 𝐻 runs over all non-trivial components of 𝐺−(𝐸𝑛𝑑(𝐺)∪𝑆𝑡𝑒𝑚(𝐺)).
Next we first show the necessity. Let 𝐷 be a minimum vertex cover set of 𝐺 with 𝑆𝑡𝑒𝑚(𝐺) ⊆ 𝐷. Clearly, 𝐷 is also a minimum dominating set of 𝐺. Let 𝐺′ = 𝐺−𝐸(⟨𝑆𝑡𝑒𝑚(𝐺)⟩𝐺), where𝐸(⟨𝑆𝑡𝑒𝑚(𝐺)⟩𝐺) denotes the edges in the induced subgraph
⟨𝑆𝑡𝑒𝑚(𝐺)⟩𝐺. Then we next show that 𝐺′ is a bipartite graph with the partite sets 𝐷 and 𝑉(𝐺)−𝐷. Since 𝐺′ is a spanning subgraph of 𝐺 without isolated vertices, then Lemma 2 yields that 𝛾(𝐺′) =𝛽(𝐺′) =∣𝐷∣. Clearly, 𝐷 is also a minimum vertex cover of𝐺′ and set𝑉(𝐺′)−𝐷is an independent set by the definition of vertex cover. Suppose that there exists an edge 𝑢𝑣 in the induced subgraph 𝐺′[𝐷]. By the construction of 𝐺′, there is at least one of {𝑢, 𝑣}, say 𝑢, which is not a stem in 𝐺. But now 𝐷− {𝑢}
is also a dominating set of 𝐺′, a contradiction. Hence, 𝐺′ is bipartite with bipartition 𝐷 and 𝑉(𝐺)−𝐷. Consequently, each component 𝐻 of 𝐺−(𝐸𝑛𝑑(𝐺)∪𝑆𝑡𝑒𝑚(𝐺)) is a trivial graph or a bipartite graph.
Since 𝐺 ∈ 𝒢𝛾=𝛽, so 𝐺 is also a member of 𝒢𝛾=𝜈 by Theorem 1. From Theorem 2,
we complete the proof. □
Acknowledgments
The authors are indebted to the anonymous referees for their constructive comments.References
[1] B. Bollob´as,Modern Graph Theory, 2nd Edition, Springer-Verlag New York, Inc.
1998.
[2] B. L. Hartnell and D. F. Rall, A characterization of graphs in which some minimum dominating set covers all the edges,Czechoslovak Math. J., 45(1995), pp. 221-230.
[3] T. W. Haynes, S. T. Hedetniemi and P. J. Slater,Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[4] M. Kano, Y. Wu and Q. Yu, Star-uniform graphs,Graphs Combin., 26(2010), pp.
383-394.
[5] B. Randerath and L. Volkmann, Characterization of graphs with equal domination and covering number, Discrete Math., 191(1998), pp. 159-169.
[6] B. Randerath and L. Volkmann, Characterization of graphs with equal domination and matching number, Utilitas Math., 55(1999), pp. 65-72.
[7] L. Volkmann, On graphs with equal domination and covering number, Discrete Appl. Math., 51(1994), pp. 211-217.
