Dominating induced matchings and other graph parameters

Abstract

A matching M in a graph G is an induced matching if the largest degree of the subgraph of G induced by M is equal to one. A dominating induced matching (DIM) of G is an induced matching that dominates every edge of G. It is well known that, if they exist, all dominating induced matchings of G are of the same size. The dominating induced matching number of G, denoted by $\text{dim}(G)$, is the size of any dominating induced matching of G. In this paper, we continue the study of dominating induced matchings. We prove that, if G has a DIM, then the induced matching number of G is equal to the independence number of its line graph L(G) and to the edge domination number of G. It is also shown that $\text{dim}(G)\le 2 \text{dim}(L(G))$, provided that both G and L(G) have a DIM. We also present some bounds on $\text{dim}(G)$. In particular, for a tree T with a DIM we show that $\lceil \frac{n-l+1}{3}\rceil \le \text{dim}(T)\le \lfloor \frac{n-1+l}{3}\rfloor$, where l is the number of leaves. Moreover, for a regular graph G we establish some Nordhaus-Gaddum type bounds.

KEYWORDS:

• Domination
• induced matching
• dominating induced matching
• maximal matching
• saturation number

1 Introduction

Adjacency and incidence are two basic concepts of graph theory. They are, in fact, so fundamental that they must be restricted in order to make them useful. It can be argued that all branches of graph theory owe their existence to various, categorical or quantitative, restrictions on certain aspects of these two basic concepts. For example, the study of regular graphs starts by requiring that all vertices be incident to the same number of edges. Simple graphs are obtained by postulating that an edge must be incident with exactly two vertices and that no two different edges can be incident with the same two vertices. Further, by forbidding adjacencies within certain sets of vertices we make these sets independent, while, by doing the same with sets of edges, one arrives at matchings. Domination is obtained by requiring that every vertex be adjacent to a vertex from a specified subset, and covers and packings can be obtained in similar ways.

In all of the above examples one can introduce further quantitative and/or categorical refinements to the basic restrictions, leading thus to various sub-branches of graph theory, each with its own lore and terminology. It is easy to see how this process could lead to narrowing the focus of research and to the loss of the wider picture.

In this paper we intend to stress the common theme and to examine the interplay of several restrictions of the considered type by studying the dominating induced matchings. In the next section, we state our assumptions about the considered graphs, introduce necessary definitions, and quote some known results needed in the subsequent sections. Section 3 contains some basic results about the considered quantities. The next two sections present our main results by putting the cardinality of dominating induced matchings in relations with other relevant graph parameters and by establishing some upper and lower bounds. In the next-to-last section, we sharpen some of our results for various classes of trees. The paper is concluded with a short section indicating some possible directions of future research.

2 Definitions and preliminary results

In this paper we consider only finite, simple and undirected graphs. For a given graph G, we denote its vertex set by $V=V(G)$, and its edge set by $E=E(G)$. The order and size of a graph G are denoted by $n=n(G)$ and $m=m(G)$, respectively. For graph theoretic terminology and notations we refer to book [27].

For every vertex $v\in V$, the open neighborhood N(v) is the set $\{u\in V|\mathit{\text{uv}}\in E\}$ and the closed neighborhood of v is the set $N[v]=N(v)\cup \left\{v\right\}$. The degree of a vertex $v\in V$ is $d(v)=|N(v)|$. The minimum and maximum degree of a graph G are denoted by δ and Δ, respectively. A graph is bipartite if its vertex set can be partitioned into two subsets X and Y such that every edge has one end in X and one end in Y. If further every vertex f in X is joined to every vertex in Y, then it is called a complete bipartite graph. By $K_{r,s}$, we denote the complete bipartite graph with $\left|X\right|=r$ and $\left|Y\right|=s$. The line graph of a graph G, written L(G), is the graph whose vertices are the edges of G, with $\mathit{\text{ef}}\in E(L(G))$ when e = uv and f = vw in G. A generalized Petersen graph P(n, k) is a graph with vertex set $\{u_0,u_1,\dots ,u_{n-1},v_0,v_1,\dots ,v_{n-1}\}$ and edge set $\{u_i{u}_{i+1},u_i{v}_i,v_i{v}_{i+k}|i=0,\dots ,n-1\}$, where subscripts are to be read modulo n and $k<n/2$. Two distinct vertices u and v are called duplicated if $N(u)=N(v)$.

A spider is a star with some of its edges subdivided by a vertex. If all edges are subdivided, we say that the spider is healthy, having all legs of equal length.

A set D of vertices in a graph G is called a dominating set if every vertex $v\in V(G)$ is either an element of D or is adjacent to an element of D. A set D of vertices in a graph G is called a total dominating set if every vertex $v\in V(G)$ is adjacent to an element of D. The domination number of a graph G, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set in G. Respectively, the total domination number of a graph G, denoted by ${\gamma }_t(G)$, is the minimum cardinality of a total dominating set in G.

An independent set is a subset of vertices in a graph such that no two vertices in it are adjacent. A maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of G, and denoted by $\alpha =\alpha (G)$. An independent dominating set is a set that is both dominating and independent. The independent domination number of G, denoted by i(G), is the minimum size of an independent dominating set. The theory of independent domination has been studied in [19] and [20].

A subset $D\subseteq E$ is an edge dominating set if each edge in E is either in D or is adjacent to an edge in D. An edge dominating set D is called a minimal edge dominating set if no proper subset F of D is an edge dominating set. The edge domination number $\gamma \prime (G)$ is the minimum cardinality among all minimal edge dominating sets [26].

A vertex cover of a graph G is a subset $S\subseteq V(G)$ that contains at least one endpoint of every edge. The number $\beta (G)$ denotes the minimum cardinality among all vertex covers in G.

An edge cover of G is a subset L of edges such that every vertex of G is incident to some edge of L. The number $\beta \prime (G)$ denotes the minimum size of an edge cover of G. It follows immediately that $\gamma \prime (G)\le \beta \prime (G)$.

A matching in a graph G is a subset of edges with no shared end-points. The vertices incident to the edges of a matching M are saturated by M. The maximum size of a matching in a graph G is denoted by $\nu (G)$. A matching of size $\nu (G)$ is called a maximum matching. A matching is perfect if it saturates all vertices of G. Obviously, perfect matchings are possible only in graphs of even order and, in such cases, $\nu (G)=n/2$.

Another way to look at matchings is by using set inclusion. A matching M is maximal if it is not a subset of any other matching of G. In other words, M cannot be extended to a valid matching in G by adding edges not yet in M. Obviously, every maximum matchings is also maximal, but the opposite claim is usually not true. Maximal matchings can (and usually do) have different sizes. The size of any smallest maximal matching is called the saturation number of G and denoted by s(G). Maximal matchings serve as useful models of various processes, ranging from parking cars along a street to random allocation of a sequential resource such as computer memory to adsorption of dimers on a structured substrate [4, 13, 14, 17, 18]. The saturation number then indicates how inefficient those processes can be in the worst case scenario. For more information on all aspects of matching theory we refer the reader to the classical monograph by Lovász and Plummer [25].

A matching M is a dominating induced matching (a DIM for short) of a graph if every edge is either in M or has a common end-vertex with exactly one edge in M. In some papers a DIM is also called an efficient edge dominating set, see for example [21]. The number of members of any two dominating induced matchings of G is the same [1]. It follows immediately from the fact that a dominating induced matching, if it exists, must be also a smallest maximal matching in the considered graph. The dominating induced matching number of G, denoted by $\text{dim}(G)$, is the size of a dominating induced matching of G. It is worth mentioning that if M is a DIM of G, then there is a partition of V(G) into two disjoint subsets V(M) and S, where S is an independent set. Conversely, if there exists a graph G such that its vertex set V(G) can be partitioned into two vertex subsets V₁ and V₂, where V₁ induces a matching and V is an independent set, then the subset $M\subset E(G)$ of edges with both ends in V₁ is a DIM. Dominating induced matching have been studied extensively in the literature such as [8, 9, 11, 12, 21, 22] and [24].

The dominating induced matchings are the main topic of the present paper. We continue the line of research started in [1] by showing that, if both G and L(G) have a DIM, then $\text{dim}(G)\le 2\text{dim}(L(G))$. Further, we provide some non-trivial bounds on $\text{dim}(G)$ and refine them for trees. Along the way we also investigate relationship between the size of a DIM of a graph and of its complement, obtaining a Nordhaus-Gaddum type result for the sum of the two quantities.

At the end of this section we quote some known results which will be useful in the rest of the paper. For the first two we also provide proofs for the reader’s convenience.

Lemma 1.

Let G be a graph. Then there exists a $\gamma \prime (G)$-set with no edges of it incident to each other.

Proof.

Suppose that S is a $\gamma \prime (G)$-set with e₁ and e₂ adjacent to each other in S. According to the minimality of S, e₁ has an adjacent edge e₃ which is not adjacent to e₂. Then $(S\setminus \{e_1\})\cup \left\{e_3\right\}$ is a $\gamma \prime (G)$-set. Repeating the process, we obtain a $\gamma \prime (G)$-set with the desired property since each of the edges in S has an adjacent edge which does not meet any other edges of S. □

Theorem 2.

Let G be a graph. Then $i(L(G))=\gamma \prime (G)$.

Proof.

One has $\gamma \prime (G)\le i(L(G))$ since every independent dominating set for L(G) is an edge dominating set for G. Assume that S is a $\gamma \prime (G)$-set. By Lemma 1, one can assume that no edges of S are adjacent to each other. Thus the corresponding vertices of the elements of S in L(G) form an independent dominating set for L(G). Hence, $i(L(G))\le \gamma \prime (G)$ and we are done. □

For proofs of the following two results we refer the reader to [3].

Proposition 3.

[3] Let G be a graph with a DIM. Then $\gamma (G)\le {\gamma }_t(G)\le 2 \text{dim}(G)$.

Remark 4.

Note that the difference between $2 \text{dim}(G)$ and ${\gamma }_t(G)$ can be arbitrarily large. Consider the healthy spider S_t with t leaves. Then $2 \text{dim}(G)-{\gamma }_t(G)=t-1$. It shows that $2 \text{dim}(G)-{\gamma }_t(G)$ can be arbitrarily large. Also, it is possible that $2 \text{dim}(G)={\gamma }_t(G)$. To see this, consider $P_{3k+1}$, where k is a positive integer.

Theorem 5.

[3] If G does not have an induced subgraph isomorphic to $K_{1,3}$, then $\gamma (G)=i(G)$.

3 Existence and basic properties

In this section, we investigate some basic properties of dominating induced matchings. First we consider the problem of their existence, since it is well known that many graphs do not have a DIM. For example, if in a graph G each edge lies on a C₄, then G does not have a DIM. This simple observation yields large classes of graphs which do not have DIM, such as prisms (the Petersen graphs $P(n,1)$) and n-dimensional hypercubes Q_n. On the other hand, one can easily present graphs with a DIM. For instance, the cycles of size 3k, $k\ge 1$, have a DIM such that $\text{dim}(C_{3k})=k$. Also, the paths with n vertices, $n\ge 2$, have a DIM and $\text{dim}(P_n)=\lceil \frac{n-1}{3}\rceil$.

We start by quoting a theorem which was proved in [1], formalizing our remark about the equal size of all DIMs.

Theorem 6.

Let G be a graph. If D₁ and D₂ are two DIMs of G, then $\left|D_1\right|=\left|D_2\right|$.

Next, we look at the generalized Petersen graphs $P(n,2)$ with $n\stackrel{5}{\equiv }0$.

Observation 7.

For the Petersen graph $P(n,2),n\stackrel{5}{\equiv }0$, we have $\text{dim}(P(n,2))=\frac{3n}{5}$

Proof.

Let $n=5t,t\ge 1$. Index the inner and the outer vertices of the Petersen graph $P(n,2)$ by $\{u_1,u_2,\dots ,u_n\}$ and $\{v_1,v_2,\dots ,v_n\}$, respectively, and select the edges $\left\{v_i{v}_{i+1}\right|i\stackrel{5}{\equiv }3\},\{v_i{u}_i\left|i\stackrel{5}{\equiv }1\right\}$ and $\left\{u_i{u}_{i+2}\right|i\stackrel{5}{\equiv }0\}$. It is easy to see that the selected edges are a DIM for $P(n,2),n\stackrel{5}{\equiv }0$. This verification in conjunction with Theorem 6 yields the assertion. □

Lemma 8.

For every integer $1\le k<\frac{n}{2}$, there exists a graph of order n with $\text{dim}(G)=k$.

Proof.

Take a matching A of size k and an independent set B with $\left|B\right|=n-2k$. Add edges connecting vertices of B to the end-vertices of edges in A so that the resulting graph G is connected. Then $\text{dim}(G)=k$. □

Some of the well-known graphs such as, e.g., the complete graphs except K₃, the complete bipartite graphs and wheel graphs do not have DIMs. Therefore, a question arises here how many edges need to be removed from them so that the remaining graph contains a DIM. In the following theorem we investigate this problem for complete graphs.

Theorem 9.

Let $\theta (G,k)$ be the minimum number of edges to be deleted from G so that the resulting graph has a DIM of size k. Then $$\theta (K_n,k)=\frac{n(n-1)}{2}-(k(2n-4k+1)).$$

Moreover, if $k=\lfloor \frac{n}{4}\rfloor$, then the number of deleted edges is minimal.

Proof.

Let us put the DIM vertices (2k vertices) on one side and the non-DIM vertices($n-2k$ vertices) on the other side and enumerate the edges. There are at most $2k(n-2k)+k$ edges between 2 parts. If we removed other edges from K_n, the size of DIM remain k. Therefore, the least number of edges needed to be deleted from a complete graph so that the remaining graph has a DIM of size k is $\Theta (k_n,k)\ge \frac{n(n-1)}{2}-(2k(n-2k)+k).$ For the last part, we need to maximize $f(k)=2k(n-2k)+k$. The maximum occurs at $k=\frac{2n+1}{8}=\lfloor \frac{n}{4}\rfloor$, which results in the minimal number of edges to be deleted. □

4 DIM versus other graph parameters

In this section, we relate $\text{dim}(G)$ to other relevant parameters of a graph G. First, we prove that the induced matching number of G is equal to the independence number of L(G) and hence to $\gamma \prime (G)$.

Theorem 10.

Let G be a graph and $S\subseteq E$a DIM for G. Then the corresponding vertices of S form a minimum independent dominating set in L(G).

Proof.

Assume first that $S=\{e_1,\dots ,e_t\}$, where $t=\text{dim}(G)$. Since S is a DIM, e_i’s are independent in L(G) and every arbitrary $e\in E(G)\setminus S$ is dominated by exactly one vertex e_i, $1\le i\le t$, in L(G). So S is an independent dominating set in L(G). Now, we show that S is a minimum independent dominating set. Assume that $A\subseteq V(L(G))$ is an independent dominating set such that $\left|A\right|<\left|S\right|$. Let $A\prime =A\setminus S$ and $S\prime =S\setminus A$. Since S is a DIM for G, we have $|A\prime |=|A\setminus S|\ge 1$. On the other hand, we have $$|S\prime |=|S\setminus A|=\left|S\right|-|A\cap S|>\left|A\right|-|A\cap S|=|A\prime |.$$

Therefore, there exist at least two vertices e_p and e_k of $S\prime$ which are dominated by a vertex e_j from $A\prime$, which is a contradiction. □

We can now state one of our main results.

Corollary 11.

Let G be a graph with a DIM. Then $$i(L(G))=\text{dim}(G)=\gamma \prime (G).$$

Proof.

It follows immediately that each DIM for a graph G is also an edge dominating set in G and hence $\gamma \prime (G)\le \text{dim}(G)$. On the other hand, by Theorems 10 and 2, one has $$\text{dim}(G)\le i(L(G))=\gamma \prime (G)\le \text{dim}(G),$$and the assertion follows. □

The following result is a direct consequence of previous Corollary.

Corollary 12.

Let G be a graph with a DIM. Then $$\frac{n-\alpha (G)}{2}\le \text{dim}(G)\le \alpha (L(G)).$$

Proposition 13.

Let G be a graph such that G and L(G) both have a DIM. Then $\mathrm{d}\mathit{\text{im}}(G)\le 2 \text{dim}(L(G))$.

Proof.

One has $\gamma (L(G))=i(L(G))=\text{dim}(G)$, by Theorem 5 and Corollary 11. So Proposition 3 implies that $\gamma (L(G))=\text{dim}(G)\le 2 \text{dim}(L(G))$. □

Proposition 14.

Let G be a graph with no isolated vertices which has a DIM. Then $n\le \beta +\beta \prime \le n+\text{dim}(G)$, and the lower bound is sharp.

Proof.

Let S be a DIM for G. Consider each vertex $v_i,1\le i\le n-2\text{dim}(G)$ in $V\setminus V(S)$ and from all the edges incident to v_i select exactly one edge e_i. Then $S\prime =S\cup \{e_1,e_2,\dots ,e_{n-2\text{dim}(G)}\}$ is an edge cover. Therefore, $\beta \prime \le n-\text{dim}(G)$. Obviously, $\beta \le 2\text{dim}(G)$. Since $\beta \prime \ge \alpha$, we have $n\le \beta +\beta \prime \le n+\text{dim}(G)$. □

5 Some upper and lower bounds

In this section, we provide several bounds on DIM. For every $e\in E(G)$, let E_e be the set of edges which are dominated by e. If G has a DIM, then $$|E(G)|=\left|{\cup }_{e\in \mathit{\text{DIM}}}{E}_e\right|=\sum _{e\in \mathit{\text{DIM}}}\left|E_e\right|\ge (2\delta -1)\text{dim}(G).$$

So we have the following result.

Lemma 15.

[10] Let G be a graph of order n with a DIM. Then $\text{dim}(G)\le \frac{|E(G)|}{2\delta -1}$. Moreover, if G is a k-regular graph, then $\text{dim}(G)=\frac{\mathit{\text{nk}}}{4k-2}$.

This result was further refined in [1] by including also the maximum degree of G. Lemma 15 helps us to characterize the graphs which have and those which do not have a DIM. Consider a healthy spider S_t, $t\ge 1$, with vertex set $\{v,v_1,v_2,\dots ,v_t,v{\prime }_1,\dots ,v{\prime }_t\}$. Let $\mathrm{F}$ be the family of all graphs G with vertex set $\{v,v_1,v_2,\dots ,v_t,v{\prime }_1,\dots ,v{\prime }_t\}$ and $E(G)=E(S_t)\cup \left\{\mathit{\text{vv}}{\prime }_i\right|\text{for some }i,1\le i\le t\}$.

Theorem 16.

Let G be a connected graph of order n with a DIM. Then the following statements hold:

1. $\text{dim}(G)=\lfloor \frac{n}{2}\rfloor$ if and only if n is odd and G is a healthy spider or $K_1\vee {\cup }_{i=1}^{\lfloor \frac{n}{2}\rfloor }{K}_2$ or $G\in \mathrm{F}$.

2. $\text{dim}(G)=1$ if and only if G contains an edge e = uv such that all other edges of G (if any) are incident to one of its end-vertices.

Proof.

Suppose that $\text{dim}(G)=\lfloor \frac{n}{2}\rfloor$ and let $\mathit{\text{DIM}}=\{e_1,e_2,\dots ,e_{\lfloor \frac{n}{2}\rfloor }\}$. Since there is no edge between the e_i, for $1\le i\le \lfloor \frac{n}{2}\rfloor$, and G is a connected graph, thus n is odd. Without loss of generality, set $\mathit{\text{DIM}}=\{e_1=v_1{v}_2,e_2=v_3{v}_4,\dots ,e_{\lfloor \frac{n}{2}\rfloor }=v_{n-2}{v}_{n-1}\}$. Hence $v_n\notin \{v_1,v_2,\dots ,v_{n-1}\}$. Three cases may happen. Assume first that v_n is adjacent to each v_i, $1\le i\le n-1$. Then G is $K_1\vee {\cup }_{i=1}^{\lfloor \frac{n}{2}\rfloor }{K}_2$. So, without loss of generality, suppose that v_n is adjacent to v_i, $1\le i\le n-1$ and i is odd. Then G is a healthy spider. Finally, it is possible that v_n is adjacent to both ends of some DIM’s edges and also is adjacent to one end of some other DIM’s edges. Therefore $G\in \mathrm{F}$. This completes the proof of (1), since the converse assertion in (1) is obvious.

The assertion (2) is straightforward. It is worth noting that the graphs it describes include stars and double stars. □

We now present an upper bound for domination induced matching number of G in terms of its size and minimum degree. The following proposition was given in [7].

Proposition 17.

For a graph G with n vertices and maximum degree Δ, $$\lceil \frac{n}{1+\Delta }\rceil \le i(G)\le n-\Delta .$$

Corollary 18.

Let G be a graph with a DIM. Then $$\text{dim}(G)\le m-2\delta (G)+2.$$

Proof.

According to Corollary 11 and Proposition 17, one has $$\text{dim}(G)=i(L(G))\le n_{L(G)}-\Delta (L(G))\le m-2\delta (G)+2.$$

□

The following theorem was shown in [5, Theorem 2.1].

Theorem 19.

Let G be a connected graph with maximum degree Δ. Then ${\gamma }_t(G)\ge \lceil \frac{n}{\Delta }\rceil$.

By using Proposition 3 in conjunction with Theorem 19, we obtain the following lower bound for $\text{dim}(G)$.

Corollary 20.

Let G be a connected graph. Then $\text{dim}(G)\ge \lceil \frac{n}{2\Delta }\rceil$.

Proposition 21.

Let G be a bipartite graph with two parts $\left|X\right|=r$ and $\left|Y\right|=s$ and a DIM. Then the following statements hold:

1. $|E(G)|\le (r+s)\text{dim}(G)-2\text{dim}{(G)}^2+\text{dim}(G)$.

2. If G is a k-regular graph, then $\text{dim}(G)\le r-k+1$.

3. For every integer k, there exists a bipartite graph with $\text{dim}(G)=k$ such that $|E(G)|=(r+s)\text{dim}(G)-2\text{dim}{(G)}^2+\text{dim}(G)$.

Proof.

Assume that $M=\{v_1{u}_1,\dots ,v_{\text{dim}(G)}{u}_{\text{dim}(G)}\}$ be a DIM for G. Without loss of generality, let $X=\{v_1,\dots ,v_{\text{dim}(\mathrm{G})},v_{\text{dim}(G)+1},\dots ,v_r\}$ and $Y=\{u_1,\dots ,u_{\text{dim}(\mathrm{G})},u_{\text{dim}(G)+1},\dots ,u_s\}$ are two parts of G. So one has $d(v_i)\le (s-\text{dim}(G))+1$, for $1\le i\le \text{dim}(G)$ and $d(v_i)\le \text{dim}(G)$, for $\text{dim}(G)+1\le i\le r$. Therefore $$\begin{array}{c}|E(G)|=\sum _{i=1}^{\text{dim}(G)}d(v_i)+\sum _{\text{dim}(G)+1}^{r}d(v_i)\\ \le \sum _{i=1}^{\text{dim}(G)}((s-\text{dim}(G))+1)+\sum _{\text{dim}(G)+1}^r\text{dim}(G)\\ \le (r+s)\text{dim}(G)-2\text{dim}{(G)}^2+\text{dim}(G).\end{array}$$

The second statement immediately follows from the first statement of this proposition and from Proposition 15. For the last assertion, put $A=\{x_1{y}_1,\dots ,x_k{y}_k\}$, the k edges which belong to DIM and $n-2k$ vertices in a set B and connect each vertex in B either to all vertices x_i or to all vertices y_i, for $1\le i\le k$. □

Corollary 22.

Let G be a graph of order n with a DIM. Then $$|E(G)|\le 2 n \text{dim}(G)-4 \text{dim}{(G)}^2+\text{dim}(G).$$

Proof.

Let M be a DIM for G and $V(G)=\{v_1,\dots ,v_n\}$. Construct an auxiliary bipartite graph B(G) with two parts, $X\prime =\{v{\prime }_1,\dots ,v{\prime }_n\}$ and $X″=\{v\prime {\prime }_1,\dots ,v\prime {\prime }_n\}$ and join $v{\prime }_i$ to $v\prime {\prime }_j$ and $v{\prime }_j$ to $v\prime {\prime }_i$ if and only if the edge $v_i{v}_j$ is in G. Suppose that $M\prime \subseteq E(B(G))$ are the corresponding edges in M. It is not hard to see that $M\prime$ is a DIM for bipartite graph B(G), $|E(B(G))|=2|E(G)|$ and $|M\prime |=2\left|M\right|$. So, by Proposition 21, $|E(B(G))|\le 2 n \text{dim}(B(G))-2 \text{dim}{(B(G))}^2+\text{dim}(B(G))$ and we are done. □

At the end of this section, we look at the relationships between DIMs of a regular graph and DIMs of its complement and obtain a so called Nordhaus-Gaddum type inequality for the dominating induced matching number of regular graphs.

Theorem 23.

Let G be an r-regular graph of order n such that both of G and $\overline{G}$ have a DIM. Then $$\text{dim}(G)+\text{dim}(\overline{G})\ge \{\begin{array}{cc}\frac{n(n-1)}{2(n-2)}\hfill & \text{ if }n\text{ is odd}\hfill \\ \frac{n(n^2-3n+1)}{2(n-1)(n-3)}\hfill & \text{ if }n\text{ is even}.\hfill \end{array}$$

Proof.

Since G is r-regular, then $\overline{G}$ is $(n-r-1)$-regular. Therefore it follows from Lemma 15 that $$\text{dim}(G)+\text{dim}(\overline{G})\ge \frac{n}{2}\left(\frac{r}{2r-1}+\frac{n-r-1}{2n-2r-3}\right).$$

Let $f(r)=\frac{r}{2r-1}+\frac{n-r-1}{2n-2r-3}$. As this function has its minimum for $r=\frac{n-1}{2}$, we obtain $$\begin{array}{c}\text{dim}(G)+\text{dim}(\overline{G})\ge \frac{n}{2}\left(\frac{r}{2r-1}+\frac{n-r-1}{2n-2r-3}\right)\\ \ge \frac{n(n-1)}{4}\left(\frac{1}{n-2}+\frac{1}{n-2}\right).\end{array}$$

If n is even, then the function f has its minimum for $r=\frac{n-2}{2}$ or $r=\frac{n}{2}$, since r is an integer. Hence one has $$\begin{array}{c}\text{dim}(G)+\text{dim}(\overline{G})\ge \frac{n}{2}\left(\frac{r}{2r-1}+\frac{n-r-1}{2n-2r-3}\right)\\ \ge \frac{n}{4}\left(\frac{n}{n-1}+\frac{n-2}{n-3}\right)=\frac{n(n^2-3n+1)}{2(n-1)(n-3)}\end{array}$$

and the proof is complete. □

From Theorem 10 and [20, Proposition 6.1], the following result is obtained.

Corollary 24.

Let G and $\overline{G}$ both have DIMs. Then $$2\le \text{dim}(G)+\text{dim}(\overline{G})\le i(L(G))+i(L(\overline{G}))\le m+1.$$

6 Trees

In this section, we consider trees and present some bounds for their dominating induced matching numbers. We use the following theorem which was proved in [2].

Theorem 25.

Let T be a tree of order n. Then $$\lceil \frac{2(n-l+1)}{3}\rceil \le \gamma {\prime }_R(T)\le \lceil \frac{2(n-1)}{3}\rceil .$$

A leaf of a graph G is a vertex of degree 1. A weak support vertex is a vertex adjacent to a leaf and a strong support vertex is a vertex adjacent to at least two leaves. Let x and y be two adjacent vertices in a tree. We denote by T_x the component of T – y containing x. We can now state the main result of this section.

Theorem 26.

Let T be a tree with a DIM, n vertices and l leaves. Then $$\lceil \frac{n-l+1}{3}\rceil \le \text{dim}(T)\le \lfloor \frac{n-1+l}{3}\rfloor .$$

Moreover, these bounds are sharp.

Proof.

For the upper bound, we apply induction on n. As the induction basis, it is easily verified that the statement holds for trees with $n\le 4$ vertices. Assume that all the trees of order smaller than n with a DIM satisfy the stated inequality. Let T be a tree of order $n\ge 5$ with a DIM. Consider x as a support vertex. Two cases happen:

Case 1. x is a strong support vertex and y is a leaf adjacent to x. Now, we must consider two subcases:

Subcase 1.1. $\mathit{\text{xy}}\in \mathit{\text{DIM}}$. Let $T\prime =T\setminus \left\{y\right\}$. Consider another leaf $y\prime$ adjacent to x. Then $\mathit{\text{DIM}}\setminus \left\{\mathit{\text{xy}}\right\}\cup \{\mathit{\text{xy}}\prime \}$ is a DIM for $T\prime$. Hence, by induction hypothesis $\text{dim}(T)=\text{dim}(T\prime )\le \lfloor \frac{(n-1)-1+(l-1)}{3}\rfloor \le \lfloor \frac{n-1+l}{3}\rfloor .$

Subcase 1.2. $\mathit{\text{xy}}\notin \mathit{\text{DIM}}$. In this case, we have a non-leaf vertex in DIM adjacent to x. Let $T\prime =T\setminus \left\{y\right\}$. Clearly, DIM is also a DIM for $T\prime$ and the statement is obtained with a similar argument as above.

Case 2. x is a weak support vertex in T and y is the only leaf adjacent to x. Two subcases arise:

Subcase 2.1. Let xy belong to DIM and $N_T(x)=\{y,x_1,x_2,\dots ,x_t\}$. Set $T\prime =T\setminus \{x,y,x_1,x_2,\dots ,x_t\}$. Clearly, $\mathit{\text{DIM}}\cap T_{x_i}$ is a DIM for $T_{x_i}$, $1\le i\le t$ and the assertion holds for any T_i by induction hypothesis. Hence we have $$\begin{array}{c}\text{dim}(T)-1=\text{dim}(T\prime )=\sum _{i=1}^t\text{dim}(T_{x_i})\\ \le \lfloor \frac{n_1-1+l_1}{3}\rfloor +\cdots +\lfloor \frac{n_t-1+l_t}{3}\rfloor \\ \le \lfloor \frac{(n-2-t)-t+(l_1+\cdots +l_t)}{3}\rfloor \\ \le \lfloor \frac{(n-2-t)-t+(l+t-1)}{3}\rfloor =\lfloor \frac{n-t+l}{3}\rfloor -1,\end{array}$$

where n_i, l_i denote the order and the number of leaves in $T_{x_i},1\le i\le t$, respectively. Hence one has $\text{dim}(\mathrm{T})\le \lfloor \frac{n-1+l}{3}\rfloor$.

Subcase 2.2. $\mathit{\text{xy}}\notin \mathit{\text{DIM}}$. Let $T\prime =T\setminus \left\{y\right\}$. Then, the DIM is a DIM for $T\prime$ and the statement follows. $\text{dim}(T)=\text{dim}(T\prime )\le \lfloor \frac{(n-1)-1+(l-1)}{3}\rfloor \le \lfloor \frac{n-l+1}{3}\rfloor .$ For the lower bound, we have $\lceil \frac{2(n-l+1)}{3}\rceil \le \gamma {\prime }_R(T)\le 2\text{dim}(T)$ by Theorems 25 and 33, proved at the very end of the paper. The bounds are sharp for paths. □

Theorem 27.

Let T be a tree with a DIM and $T\prime$ be a tree obtained from T by removing all leaves adjacent to every strong support vertex except one leaf. Then $T\prime$ has a DIM and $\text{dim}(T)=\text{dim}(T\prime )$.

Proof.

Suppose that M is a DIM for T and select arbitrary pendant edge e. Either $e\in M$, or $e\notin M$. In both cases, remove all pendant edges adjacent to e and obtain $T\prime$. Obviously, $T\prime$ has a DIM and $\text{dim}(T)=\text{dim}(T\prime )$. □

We have the following result by Theorems 26 and 27.

Corollary 28.

Let T be a tree with s strong vertices and a DIM. Then $\text{dim}(T)\le \lfloor \frac{n-1+s}{3}\rfloor$.

Theorem 29.

Let T be a tree with a DIM. Then $\text{dim}(T)\ge \lceil \frac{\text{diam}(\mathrm{T})}{3}\rceil$. Moreover, this bound is sharp.

Proof.

Suppose that $P:=v_0{v}_1{v}_2\cdots v_{\text{diam}(\mathrm{T})}$ be a diametral path. For $0\le i\le \lceil \frac{\text{diam}(\mathrm{T})}{3}\rceil$, let $P^i=v_{3i}{v}_{3i+1}{v}_{3i+2}{v}_{3i+3}$. The edge $v_{3i+1}{v}_{3i+2}$ either belongs to DIM or is dominated by one of its neighbors. So for $0\le i\le \lceil \frac{\text{diam}(\mathrm{T})}{3}\rceil$, there exists at least one DIM edge corresponding to each Pⁱ. To show the sharpness, consider $K_{1,t}$ and also all the paths. □

The following theorem has been proved in [23].

Theorem 30.

If T is a tree of order $n\ge 4$ without duplicated leaves, then $\alpha (T)\le \lfloor \frac{2n-1}{3}\rfloor$.

Theorem 31.

Let T be a tree of order $n\ge 4$, without duplicated leaves and with a DIM. Then $\text{dim}(T)\ge \lceil \frac{n+1}{6}\rceil$.

Proof.

Corollary 12 in conjunction with Theorem 30 implies that $\text{dim}(T)\ge \frac{n-\alpha (T)}{2}\ge \frac{n-\lfloor \frac{2n-1}{3}\rfloor }{2}=\frac{\lceil \frac{n+1}{3}\rceil }{2}.$ Since $\text{dim}(T)$ is an integer, we have $\text{dim}(T)\ge \lceil \frac{n+1}{6}\rceil$. □

A binary tree is a rooted tree in which every vertex has at most two children. Also, the level of v, l(v), in a rooted tree, is the largest distance from v to root.

Corollary 32.

Binary trees with $l\ge 4$ levels do not have DIM.

Proof.

A binary tree with 4 levels does not have a DIM and it is an induced subtree of any greater trees which implies that this part will never be dominated by any outer edges and therefore the statement is obtained. □

7 Concluding remarks

In this section, we indicate some possible directions of future research. To start with, one could try and adapt the arguments used in the section about trees so that they work first for unicyclic graphs, then for other graphs of low cyclomatic number and then for some classes of cacti. Alternatively, one could consider various decorations on trees and on graphs with low cyclicity.

Another thing worth trying could be to see whether the concepts such as forcing sets and forcing numbers, applicable to maximal matchings, could be meaningfully extended also to DIMs.

A natural thing to do would be to consider packings, which are generalizations of matchings, and to study dominating induced packings. Such structures have been investigated in the context of fullerene graphs, where they appeared as perfect pseudomatchings [15, 16]. It would be interesting to study such structures in wider contexts. Also, one could stay at dominating induced matchings in fullerenes and ask if they exist in various generalizations such as, e.g., ones considered in [6].

Finally, one might obtain interesting results by looking at various refinements of the concept of domination. We conclude the section and the paper by establishing a result about the edge Roman domination. (For historical roots of the concept we refer the reader to a very entertaining paper by ReVelle [28]. See also [2] for some recent results.)

An edge Roman dominating function of a graph G is a function $f:E(G)\to \{0,1,2\}$ satisfying the condition that every edge e with f(e) = 0 is adjacent to some edge $e\prime$ with $f(e\prime )=2$. The edge Roman domination number of G, denoted by $\gamma {\prime }_R(G)$, is the minimum weight $w(f)=\sum _{e\in E(G)}f(e)$ of an edge Roman dominating function f of G.

In the next theorem, we establish an inequality between the dominating induced matching number and the Roman edge domination number of G.

Theorem 33.

Let G be a graph with a DIM. Then $$\text{dim}(G)\le \gamma {\prime }_R(G)\le 2\text{dim}(G).$$

Proof.

For the first inequality, note that for each edge of DIM and its neighbors we need to use at least one 1 or 2 in Roman edge domination, and because edges of DIM have no shared neighbors, therefore $\text{dim}(G)\le \gamma {\prime }_R(G)$. Note that the equality holds if G is the union of single edges. For the second inequality, it is sufficient to label all edges of DIM by 2 and all other edges by zero. Clearly, this labeling satisfies the conditions of edge Roman domination. □

Additional information

Funding

T. Došlić gratefully acknowledges partial support of the Croatian Science Foundation via research project LightMol (Grant no. IP-2016-06-1142) and of Slovenian ARRS via grants J1-3002 and P1-0383.