This work is licensed under the Creative Commons Attribution 4.0 Public License.
Introduction
All graphs considered in this paper are finite, simple and undirected. In particular, these graphs do not have loops. Let G = (V, E) be a graph with the vertex set V(G) = {v1, v2, v3, ⋯, vn} and the edge set E(G) = {e1, e2, e3, ⋯, em}, that is |V(G)| = n and |E(G)| = m. The vertex u and v are adjacent if uv ∈ E(G). The open(closed) neighborhood of a vertex v ∈ V(G) is N(v) = {u : uv ∈ E(G)} and N[v] = N(v) ∪ {v} respectively. The degree of a vertex v ∈ V(G) is denoted by dG(v) and is defined as dG(v) = |N(v)|. A vertex v ∈ V(G) is pendant if |N(v)| = 1 and is called supporting vertex if it is adjacent to pendant vertex. Any vertex v ∈ V(G) with |N(v)| > 1 is called internal vertex. If dG(v) = r for every vertex v ∈ V(G), where r ∈ ℤ+ then G is called r-regular. If r = 2 then it is called cycle graph Cn and for r = 3 it is called the cubic graph. A graph G is unicyclic if |V| = |E|. A graph G is called a block graph, if every block in G is a complete graph. For undefined terminologies we refer the reader to [16].
A subset D ⊆ V(G) is called dominating set if N[D] = V(G). The minimum cardinality of such a set D is called the domination number γ(G) of G. A dominating set D is connected if the subgraph induced by D is connected. The minimum cardinality of connected dominating set D is called the connected dominating number γc(G) of G [27].
The energy E(G) of a graph G is equal to the sum of the absolute values of the eigenvalues of the adjacency matrix of G. This quantity, introduced almost 30 years ago [13] and having a clear connection to chemical problems [15], has in newer times attracted much attention of mathematicians and mathematical chemists [3, 8, 9, 10, 11, 12, 20,22, 23, 24, 28, 30, 31].
In connection with energy (that is defined in terms of the eigenvalues of the adjacency matrix), energy-like quantities were considered also for the other matrices: Laplacian [15], distance [17], incidence [18], minimum covering energy [1] etc. Recall that a great variety of matrices has so far been associated with graphs [4, 5, 10, 29].
Recently in [25] the authors have studied the dominating matrix which is defined as:
Let G = (V, E) be a graph with V(G) = {v1, v2, ⋯, vn} and let D ⊆ V(G) be a minimum dominating set of G. The minimum dominating matrix of G is the n × n matrix defined by AD(G) = (aij), where aij = 1 if vivj ∈ E(G) or vi = vj ∈ D, and aij = 0 if vivj ∉ E(G).
The characteristic polynomial of AD(G) is denoted by fn(G, μ) := det(μI – AD(G)).
The minimum dominating eigenvalues of a graph G are the eigenvalues of AD(G). Since AD(G) is real and symmetric, its eigenvalues are real numbers and we label them in non-increasing order μ1 ≥ μ2 ≥ ⋯ ≥ μn. The minimum dominating energy of G is then defined as
Motivated by dominating matrix, here we define the minimum connected dominating matrix abbreviated as (c-dominating matrix). The c-dominating matrix of G is the n × n matrix defined by ADc(G) = (aij), where
The characteristic polynomial of ADc(G) is denoted by fn(G, λ) := det(λ I – ADc(G)).
The c-dominating eigenvalues of a graph G are the eigenvalues of ADc(G). Since ADc(G) is real and symmetric, its eigenvalues are real numbers and we label them in non-increasing order λ1 ≥ λ2 ≥ ⋯ ≥ λn. The c-dominating energy of G is then defined as
By direct calculation, we get the minimum connected dominating eigenvalues are λ1 = 2.945, λ2 = 2.596, λ3 = 1.896, λ4 = 1.183, λ5 = –1.263, λ6 = –1.152, λ7 = 0.579, λ8 = 0.000, λ9 = –0.268 and λ10 = –0.516.
Therefore, the minimum connected dominating energy is EDc(T) = 12.398.
Example 3
The c-dominating energy of the following graphs can be calculated easily:
EDc(Kn) = (n – 2) + $\begin{array}{}
\sqrt{n(n-2) + 5}
\end{array}$, where Kn is the complete graph of order n.
EDc(K1,n–1) = $\begin{array}{}
\sqrt{4n-3}
\end{array}$ where K1,n–1 is the star graph.
EDc(Kn×2) = (2n – 3) + $\begin{array}{}
\sqrt{4n(n-1)-9}
\end{array}$, where Kn×2 is the coctail party graph.
In this paper, we are interested in studying the mathematical aspects of the c-dominating energy of a graph. This paper has organized as follows: The section 1, contains the basic definitions and background of the current topic. In section 2, we show the chemical applicability of c-dominating energy for molecular graphs G. The section 3, contains the mathematical properties of c-dominating energy. In the last section, we have characterized, trees, unicyclic graphs and cubic graphs and block graphs with equal minimum dominating energy and c-dominating energy. Finally, we conclude this paper by posing an open problem.
Chemical Applicability of EDc(G)
We have used the c-dominating energy for modeling eight representative physical properties like boiling points(bp), molar volumes(mv) at 20∘C, molar refractions(mr) at 20∘C, heats of vaporization (hv) at 25∘C, critical temperatures(ct), critical pressure(cp) and surface tension (st) at 20∘C of the 74 alkanes from ethane to nonanes. Values for these properties were taken from http://www.moleculardescriptors.eu/dataset.htm. The c-dominating energy EDc(G) was correlated with each of these properties and surprisingly, we can see that the EDc has a good correlation with the heats of vaporization of alkanes with correlation coefficient r = 0.995.
The following structure-property relationship model has been developed for the c-dominating energy EDc(G).
where$\begin{array}{}
\alpha(n) = n [\frac{n}{2}](1-\frac{1}{n}[\frac{n}{2}])
\end{array}$, where [x] denotes the integer part of a real numberk.
Proof
Let a1, a2, ⋯, an and b1, b2, ⋯, bn be real numbers for which there exist real constants a, b, A and B, so that for each i, i = 1, 2, ⋯, n, a ≤ ai ≤ A and b ≤ bi ≤ B. Then the following inequality is valid (see [6]).
where $\begin{array}{}
\alpha(n) = n [\frac{n}{2}](1-\frac{1}{n}[\frac{n}{2}])
\end{array}$. Equality holds if and only if a1 = a2 = ⋯ = an and b1 = b2 = ⋯ = bn.
We choose ai := |λi|, bi := |λi|, a = b := |λn| and A = B := |λ1|, i = 1, 2, ⋯, n, inequality (4) becomes
Let a1, a2, ⋯, an and b1, b2, ⋯, bn be real numbers for which there exist real constants r and R so that for each i, i = 1, 2, ⋯, n holds rai ≤ bi ≤ Rai. Then the following inequality is valid (see [11]).
Ifλ1(G) is the largest minimum connected dominating eigenvalue ofADc(G), then$\begin{array}{}
\lambda_1 \ge \frac{2m+\gamma_c(G)}{n}.
\end{array}$
Proof
Let X be any non-zero vector. Then we have $\begin{array}{}
\lambda_1(A) = max_{_{X \ne 0}} \{\frac{X' A X}{X' X}\},
\end{array}$ see [16]. Therefore, λ1(ADc(G)) ≥ $\begin{array}{}
\frac{J'AJ}{J'J} = \frac{2m+\gamma_c(G)}{n}.
\end{array}$□
Next, we obtain Koolen and Moulton’s [19] type inequality for EDc(G).
Theorem 10
IfGis a graph of ordernand sizemand 2m + γC(G) ≥ n, then
Since (2m + k) ≥ n, we have $\begin{array}{}
\sqrt{\frac{2m+\gamma_{c}(G)}{n}} \le \frac{2m+\gamma_c(G)}{n} \le \lambda_1.
\end{array}$ Also $\begin{array}{}
f(\lambda_1) \le f\bigg(\frac{2m+\gamma_c(G)}{n} \bigg).
\end{array}$
Graphs with equal Dominating and c-Dominating Energy
Its a natural question to ask that for which graphs the dominating energy and c-dominating energy are equal. To answer this question, we characterize graphs with equal dominating energy and c-dominating energy. The graphs considered in this section are trees, cubic graphs, unicyclic graphs, block graphs and cactus graphs.
Theorem 11
LetG = Tbe a tree with at least three vertices, thenED(G) = EDc(G) if and only if every internal vertex ofTis a support vertex.
Proof
Let G = T be a tree of order at least 3. Let F = {u1, u2, ⋯, uk} be the set of internal vertices of T. Then clearly F is the minimal dominating set of G. Therefore in AD(G) the values of ui = 1 in the diagonal entries. Further, observe that 〈F〉 is connected. Hence F is the minimal connected dominating set. Therefore, AD(G) = ADc(G). In general, AD(G) = ADc(G) is true if every minimum dominating set is connected. In other words, AD(G) = ADc(G) if γ(G) = γc(G). Therefore, the result follows from Theorem 2.1 in [2].□
In the next three theorems we characterize unicyclic graphs with AD(G) = ADc(G). Since, AD(G) = ADc(G) if γ(G) = γc(G). Therefore, the proof of our next three results follows from Theorem 2.2, Theorem 2.4 and Theorem 2.5 in [2].
Theorem 12
LetGbe a unicyclic graph with cycleC = u1u2 ⋯, unu1n ≥ 5 and letX = {v ∈ C : dG(v) ≥ 2}. ThenED(G) = EDc(G) if the following conditions hold:
(a). Everyv ∈ V – N[X] withdG(V) ≥ 2 is a support vertex.
(b). 〈X〉 is connected and |X| ≤ 3.
(c). If 〈X〉 = P1orP3, both vertices inN(X) of degree at least 3 are supports and if 〈X〉 = P2, at least one vertex inN(X) of degree at least three is a support.
Theorem 13
LetGbe unicyclic graph with |V(G)| ≥ 4 containing a cycleC = C3, and letX = {v ∈ C : dG(v) = 2}. ThenED(G) = EDc(G) if the following conditions hold:
(a). Everyv ∈ V – N[X] withdG(V) ≥ 2 is a support vertex.
(b). There exists some uniquev ∈ CwithdG(v) ≥ 3 or for everyv ∈ CofdG(v) ≥ 3 is a support.
Theorem 14
LetGbe unicyclic graph with |V(G)| ≥ 5 containing a cycleC = C4, and letX = {v ∈ C : dG(v) = 2}. ThenED(G) = EDc(G) if the following conditions hold:
(a). Everyv ∈ V – N[X] withdG(V) ≥ 2 is a support vertex.
(b). If |X| = 1, all the three remaining vertices ofCare supports and if |X| ≥ 2, Ccontains at least one support.
Theorem 15
LetGbe a connected cubic graph of ordern, ThenED(G) = EDc(G) ifG ≅ K4, C6,K3,3, G1orG2whereG1andG2are given in Fig. 4.
Theorem 16
LetGbe a block graph of withl ≥ 2. ThenED(G) = EDc(G) if every cutvertex ofGis an end block cutvertex.
Proof
Since ED(G) = EDc(G) if γ(G) = γc(G). Therefore, the result follows from Theorem 2 in [7].□
We conclude this paper by posing the following open problem for the researchers:
Open Problem: Construct non- cospectral graphs with unequal domination and connected domination numbers having equal dominating energy and c-dominating energy.