On the first Zagreb index of graphs with Self-Loops

Abstract

Some of the most comprehensively studied degree-based topological indices are the Zagreb indices. The first Zagreb index $M_1(G)$ of a graph G is defined as the sum of squares of the degrees of the vertices. Let $X\subseteq V(G)$ and let $G_X$ be the graph obtained from the simple graph G, by attaching a self-loop to each of its vertices belonging to X. In this article, some sharp bounds for the first Zagreb index of graphs with self-loops using various parameters has been put forward.

KEYWORDS:

• Zagreb index
• graph with self-loops
• sum of squares of the degrees
• Nordhaus-Gaddum type of bound

AMS CLASSIFICATION:

• 05C92
• 05C35
• 05C07

1 Introduction

Let $G=(V,E)$ be a simple connected undirected graph of order n and size m. Here, $V=V(G)=\{v_1,v_2,\dots ,v_n\}$ be the vertex set of G and $E=E(G)$ is used to denote the edge set of G. By $v_i\sim v_j$, we mean that $v_i$ is adjacent to $v_j$ (or $v_i{v}_j\in E(G)$) and by $v_i\nsim v_j$, we mean that $v_i$ is not adjacent to $v_j$ (or $v_i{v}_j\notin E(G)$). The open neighborhood of a vertex v in a graph G, denoted by $N_G(v)$ or simply $N(v)$ (if there is no confusion in the graph considered), is the set of all vertices adjacent to v in G, while the closed neighborhood of a vertex v, denoted by N[v] is given by $N(v)\cup \left\{v\right\}$. Other undefined notation and terminology of graph theory can be found in [12].

Energy of simple graphs have been much studied, where as the energy of graphs with loops was recently introduced by Ivan Gutman et al. [5]. Let $X\in V(G)$ and let $G_X$ be the graph obtained from the simple graph G, by attaching a self-loop to each of its vertices belonging to X. The degree of each vertex $v_i\in X$ in the resulting graph $G_X$ is denoted by $d(v_i)=d_i$ and is given by $d(v_i)=d^{\prime }(v_i)+2$, where $d^{\prime }(v_i)=d_i^{\prime }$ is the degree of $v_i$ in the simple graph G. If $v_i\in X$, we can write it as $v_i\sim v_i$ and $N(v_i)=N[v_i]$, and if $v_i\notin X$ then $N(v_i)\cup \left\{v_i\right\}=N[v_i]$. Let $\overline{G}$ denote the complement of the simple graph G. By $\overline{G_X}$, we mean the complement of the graph $G_X$ which is obtained by $\overline{G}$ by attaching a self loop at each vertex of $V(G)\setminus X$. The adjacency matrix of $G_X$ is a symmetric square matrix $A(G_X)$ of order n, whose ${(i,j)}^{th}$- element is defined as $$A{(G_X)}_{ij}=\{\begin{array}{cc}1,\hfill & \text{if }{v}_i\sim v_j\hfill \\ 0,\hfill & \text{if} {\mathrm{v}}_{\mathrm{i}}\nsim {\mathrm{v}}_{\mathrm{j}}\hfill \\ 1,\hfill & \text{if} i=j \text{and} v_i\in X\hfill \\ 0,\hfill & \text{if} i=j \text{and} v_i\notin X\hfill \end{array}.$$

Suppose ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ are the eigenvalues of $A(G_X)$. Then energy of $G_X$ is defined[5] as $$E(G_X)=\sum _{i=1}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|.$$

Readers are referred to [1, 5, 8, 10] for more results on energy of graphs with loops.

One of the oldest graph invariant is the well-known Zagreb index first introduced in [6]. The first Zagreb index denoted by $M_1=M_1(G)$ is defined as $$M_1=M_1(G)=\sum _{v_i\in V(G)}{d}_i^{\prime 2}=\sum _{v_i\sim v_j}(d_i^{\prime }+d_j^{\prime }).$$

For detailed summary of this index one can refer [3, 4, 9].

Similarly, the first Zagreb index of the graph $G_X$ denoted by $M_1(G_X)$ is defined as $$\begin{array}{cc}{M}_1(G_X)=\sum _{v_i\in V(G_X)}{d}_i^2=\sum _{v_i\sim v_j, i\ne j}(d_i+d_j)\hfill & \hfill \\ \hspace{1em}+\sum _{v_i\in X}2d_i=\sum _{v_i\sim v_j}(d_i+d_j).\hfill & \hfill \end{array}$$

In this paper the study is restricted only to the first Zagreb index of graphs with self-loops. In Section 2, we discuss few preliminary results which are used in the later sections. Sections 3 and 4 deals with few upper bounds and lower bounds of the first Zagreb index of graphs with self loops respectively.

2 Preliminary results

We note few preliminary results which we are using in the next sections.

Lemma 1.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$ and $\left|X\right|=\sigma$. Then $$M_1(G_X)=\sum _{u\in V(G_X)}\sum _{v\in N(u)}d(v)+\sum _{u\in X}d(u).$$

Proof.

It follows by observing that $N[u]=N(u)$, if $u\in X$. ▪

Lemma 2.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$ and $\left|X\right|=\sigma$. Then $$M_1(G_X)\le 4{(m+\sigma )}^2.$$

Proof.

The proof follows directly from the inequality, $$\sum _{i=1}^n{d}_i^2\le {\left(\sum _{i=1}^n{d}_i\right)}^2.$$

Lemma 3.

[5] Let $G_X$ be a graph of order n and size m with $\sigma$ self-loops. Let ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ be the eigenvalues of $A(G_X)$. Then $$\sum _{i=1}^n{\lambda }_i^2=2m+\sigma ,$$and $$\sum _{i=1}^n{\left|{\lambda }_i-\frac{\sigma }{n}\right|}^2=2m+\sigma -\frac{{\sigma }^2}{n}.$$

Theorem 1.

[7] Let $a=(a_1,\dots ,a_n)$ and $b=(b_1,\dots ,b_n)$ be n-tuples of real numbers satisfying $$\begin{array}{c}0\le m_1\le a_i\le M_1\\ 0\le m_2\le b_i\le M_2.\end{array}$$

Then, $$\sum _{i=1}^n{a}_i^2\sum _{i=1}^n{b}_i^2-{\left(\sum _{i=1}^n{a}_i{b}_i\right)}^2\le \frac{n^2}{3}{[M_1{M}_2-m_1{m}_2]}^2.$$

A matrix is said to be row-regular if its row sums are equal and, it is column-regular if its column sums are equal. A matrix is regular if it is both row-regular and column-regular.

A matrix A is said to be a semi-regular matrix, if there exist a permutation matrix P such that $P^{t}AP=\left[\begin{array}{cc}0& B\\ C& 0\end{array}\right]$, where B and C are regular matrices.

Theorem 2.

[2] Let $A=(a_{ij})$ be an $n\times n$ non-negative symmetric matrix with positive row sums $s_1,s_2,\dots ,s_n$. Then, the spectral radius ${\lambda }_1(A)$ satisfies, $${\lambda }_1(A)\ge \sqrt{\frac{\sum _{i=1}^n{s}_i^2}{n}}$$with equality if and only if A is regular or semi-regular.

Theorem 3.

[14] Let G be a connected graph on $n\ge 4$ vertices with a connected $\overline{G}$. Then, $$M_1(G)+M_1(\overline{G})\le n^3-4n^2+3n+8,$$with equality if and only if G or $\overline{G}$ is the graph $S_n^{\prime }$, which is obtained by attaching a pendant vertex to a pendant vertex of the star $S_{n-1}$.

Theorem 4.

[13] Let G be a $K_{\omega +1}$-free graph with n vertices and $m>0$ edges, where $2\le \omega \le n-1$. Then $$M_1(G)\le \frac{2\omega -2}{\omega }nm.$$

Lemma 4.

[11] Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$ with $\left|X\right|=\sigma$. If ${\left\{{\lambda }_i\right\}}_{1\le i\le n}$ are the eigenvalues of the adjacency matrix of the graph $G_X$, then $$\sum _{i<j}\left|{\lambda }_i-\frac{\sigma }{n}\right|\left|{\lambda }_j-\frac{\sigma }{n}\right|\ge m+\frac{\sigma (n-\sigma )}{2n},$$with equality if and only if $G_X$ is a totally disconnected graph with $\sigma =0$ or $$.

Theorem 5.

[11] Let $G_X$ be graph obtained by a simple graph G by attaching a self-loop at each vertex of $X\subseteq V(G)$ and $\left|X\right|=\sigma$. Then the spectral radius ${\lambda }_1(G_X)$ of the graph $G_X$ satisfies $$\frac{2m+\sigma }{n}\le {\lambda }_1(G_X)\le \sqrt{2m+\sigma },$$and the equality in both inequalities is attained when $G=K_n\text{ and }\sigma =n$.

3 Upper bounds

In this section, several upper bounds for $M_1(G_X)$ have obtained.

Theorem 6.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$ with $\left|X\right|=\sigma$, and let $\Delta$ and $\delta$ be the maximum and minimum degree of the graph $G_X$. Then $$M_1(G_X)\le \frac{4{(m+\sigma )}^2}{n}+\frac{n{(\Delta -\delta )}^2}{3}.$$

Proof.

By substituting $a_i=d_i$ and $b_i=1$ in Theorem 1, we get $$\begin{array}{c}\begin{array}{cc}n\sum _{i=1}^n{d}_i^2-{\left(\sum _{i=1}^n{d}_i\right)}^2\hfill & \le \frac{n^2}{3}{(\Delta -\delta )}^2\hfill \end{array}\\ \begin{array}{cc}\sum _{i=1}^n{d}_i^2\hfill & \le \frac{{\left(\sum _{i=1}^n{d}_i\right)}^2}{n}+\frac{n}{3}{(\Delta -\delta )}^2\hfill \end{array}\end{array}$$

Hence the inequality. ▪

The following result gives the bounds for $M_1(G_X)$ in terms of spectral radius of $A(G_X).$

Theorem 7.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$ with $\left|X\right|=\sigma$. If ${\lambda }_1(G_X)$ is the largest eigenvalue of $A(G_X)$, then $$M_1(G_X)\le n({\lambda }_1^2(G_X)-1)+4(m+\sigma )$$with equality if and only if $G_X$ is a regular with $\sigma =n$.

Proof.

From Theorem 2, we have $${\lambda }_1^2(G_X)\ge \frac{\sum _{i=1}^n{(d_i-1)}^2}{n},$$from which the inequality follows.

For the case of equality, it is easy to observe that $\sigma$ must be equal to n. From Theorem 2, the equality in the above follows if and only if the adjacency matrix is regular or semi-regular. But, if $\sigma =n$ then there does not exist any permutation matrix P such that $P^{t}A(G_X)P=\left[\begin{array}{cc}0& B\\ C& 0\end{array}\right]$, where B and C are regular matrices of different order. Therefore, for the equality, $G_X$ must be a regular graph with $\sigma =n$. ▪

Theorem 8.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$, with $\left|X\right|=\sigma$. If $E(G_X)$ is the energy of $A(G_X)$, then $$M_1(G_X)\le n{\left(E(G_X)\right)}^2-2m(n-2)-\sigma (n-2\sigma -4)-n.$$

Proof.

Consider, $$\begin{array}{c}{(E(G_X))}^2\hfill \\ \hspace{1em}={\left(\sum _{i=1}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|\right)}^2\hfill \\ \hspace{1em}=\sum _{i=1}^n{\left|{\lambda }_i-\frac{\sigma }{n}\right|}^2+2\sum _{i<j}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|\left|{\lambda }_j-\frac{\sigma }{n}\right|\hfill \\ \hspace{1em}=2m+\sigma -\frac{{\sigma }^2}{n}+2\sum _{i<j}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|\left|{\lambda }_j-\frac{\sigma }{n}\right|(\text{By}\text{Lemma}3)\hfill \\ \hspace{1em}\ge 2m+\sigma -\frac{{\sigma }^2}{n}+2m+\frac{\sigma (n-\sigma )}{n}(\text{By}\text{Lemma}4)\hfill \end{array}$$ $$\begin{array}{cc}\ge {\lambda }_1^2(G_X)+2m+\frac{\sigma (n-2\sigma )}{n}\hfill & (\text{By Theorem} 5)\hfill \\ \ge \frac{M_1(G_X)-4(m+\sigma )+n}{n}\hfill & \hfill \\ \hspace{1em}+2m+\frac{\sigma (n-2\sigma )}{n}(\text{By Theorem} 7)\hfill & \hfill \end{array}$$

Therefore, $M_1(G_X)\le n{(E(G_X))}^2-2m(n-2)-\sigma (n-2\sigma -4)-n.$ ▪

Similar to Theorem 3, Nordhaus-Gaddum type of upper bound is obtained in the following theorem.

Theorem 9.

Let $G_X$ be a graph obtained from a simple connected graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$, with $\left|X\right|=\sigma$. If $\overline{G_X}$ is also connected then, $$M_1(G_X)+M_1(\overline{G_X})\le n(n^2-1)+4,$$with equality if and only if either $G_X$ or $\overline{G_X}$ is isomorphic to $S_n^{*}$, where $S_n^{*}$ is a graph obtained from the star $S_{n-1}$, by attaching a self-loop to the central vertex and a pendant edge to any one of the pendant vertex.

Proof.

$$\begin{array}{c}{M}_1(G_X)+M_1(\overline{G_X})\\ \hspace{1em}=\sum _{u\in V(G_X)}\left[d^2(u)+{(n+1-d(u))}^2\right]\\ \hspace{1em}=n{(n+1)}^2+\sum _{u\in V(G_X)}\left[2d^2(u)-2nd(u)-2d(u)\right]\\ \hspace{1em}=n{(n+1)}^2-2\sum _{u\in V(G_X)}\left[d(u)(n+1-d(u))\right].\end{array}$$

Since both $G_X$ and $\overline{G_X}$ are connected, we have $d(u)(n+1-d(u))\ge n$ with equality if and only if $d(u)=1$ or $d(u)=n$. That is, the number of vertices having degree either equal to 1 (pendant vertex) or equal to n (must contain a loop) must be maximum. Let us suppose that, $u_1{u}_2$ be an edge in G with $d(u_1)=1$ and $d(u_2)=n$. Then there exist a unique vertex $u_3$ which is not adjacent to $u_2$ and $1\le d(u_3)\le n-1$. If $d(u_3)=1$ and the graph induced by $N(u_2)\setminus \{u_1,u_2\}$ is an empty graph, then $G=S_n^{*}$. Similarly, if $d(u_3)=n-1$ and the graph induced by $N(u_2)\setminus \{u_1,u_2\}$ is a clique with self-loop on each vertices, then $G=\overline{S_n^{*}}$. Other than these two cases, there will always be at least two vertices with degree at least 2 and at most $n-1$. Hence $\sum _{u\in V(G_X)}\left[d(u)(n+1-d(u))\right]$ attains minimum value when G is $S_n^{*}$ or $\overline{S_n^{*}}$ and the minimum value is equal to $n^2+n-2$. Hence, $$M_1(G_X)+M_1(\overline{G_X})\le n{(n+1)}^2-2(n^2+n-2)=n(n^2-1)+4.$$

Theorem 10.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$, with $\left|X\right|=\sigma$. Then $$M_1(G_X)+M_1(\overline{G_X})\le n^2{(n+1)}^2+4(m+\sigma )(2(m+\sigma )-n(n+1)).$$

Proof.

From Lemma 2, we have $$M_1(\overline{G_X})\le {(n(n+1)-2(m+\sigma ))}^2.$$

Hence the proof. ▪

Let G[N[u]] be the subgraph of G induced by the vertices of N[u]. Let $c_u$ denote the total number of edges and self-loops in G[N[u]] and $e_u$ denote the total number of edges that connect the vertices of $N[u]\setminus \left\{u\right\}$ with the vertices of $\left\{V(G)\setminus (N[u]\setminus \left\{u\right\})\right\}$. Now, $\sum _{v\in N[u]}{d}_v=2c_u+e_u$, and $e_u\le m+(d_u-1)-c_u.$ Then, $$\sum _{v\in N\left[u\right]}{d}_v\le c_u+m+d_u-1,$$with equality for $d_u>2$ if and only if either $V(G)\setminus \left\{u\right\}\subseteq N[u]$ or $G[V(G)\setminus N[u]]$ is a totally disconnected graph with or without self-loops.

Theorem 11.

Let G be a connected $K_{\omega +1}$-free graph with n vertices and $m>0$ edges, where $2\le \omega \le n-1$ and let $G_X$ be the graph obtained from G by attaching a self-loop at each vertex of $X\subseteq V(G),$ with $\left|X\right|=\sigma$. Then, $$M_1(G_X)\le 8(m+n)+(2m-4)n-\frac{2mn}{\omega }$$with equality if and only if $G_X$ is a complete bipartite graph with $\sigma =n$ for $\omega =2$ and a balanced complete $\omega$-partite graph with $\sigma =n$ for $\omega >2$.

Proof.

We know that $M_1(G_X)\ge M_1(G)$ with equality if and only if X is an empty set. In order to find the maximum value of $M_1(G_X$), without loss of generality, let us assume that $X=V(G)$. Let u be any vertex in $G_X$, then $d(u)=d_u\ge 2$.

Now, $G[N(u)\setminus \{u\}]$ can not contain $K_{\omega }$ as a subgraph. Therefore, by using Turan’s theorem we have, the maximum number of edges in a $K_{\omega -1}$-free graph is $$\frac{(\omega -2)(n^2-s^2)}{2\omega -2}+\left(\begin{array}{c}s\\ 2\end{array}\right),$$where s is the residual number of vertices in the balanced ($s=0$) or nearly balanced ($1\le s\le \omega -1$) complete $\omega -1$-partite graph. Hence, $$c_u\le \frac{\omega -2}{2\omega -2}{(d_u-2)}^2+(d_u-1)+(d_u-2),$$ with equality if and only if $G[N(u)\setminus \{u\}]$ is a complete $\omega -1$ partite graph on $(d_u-2)$ vertices we get, $$\begin{array}{c}\sum _{u\in V}{d}_v+d_u\\ \le c_u+m+2d_u-1\\ =\left(\mathrm{}\frac{\omega -2}{2\omega -2}{(d_u-2)}^2+(d_u-1)+(d_u-2)\mathrm{}\right) + m+2d_u-1\\ =\left[\mathrm{}\frac{\omega -2}{2\omega -2}\mathrm{}\right]d_u^2-4d_u\left[\mathrm{}\frac{\omega -2}{2\omega -2}-1\mathrm{}\right]+\left[\mathrm{}\frac{4(\omega -2)}{2\omega -2}-4+m\mathrm{}\right]\mathrm{}.\end{array}$$

By using Lemma 1, we have $$\begin{array}{cc}{M}_1(G_X)=\sum _{u\in V}\left[\left(\sum _{v\in N\left[u\right]}d(v)\right)+d(u)\right]\hfill & \hfill \\ \le \sum _{u\in V}(\left[\frac{\omega -2}{2\omega -2}\right]d_u^2+\left[4-\frac{4(\omega -2)}{2\omega -2}\right]d_u\hfill & \hfill \\ \hspace{1em}+\left[m-4+\frac{4(\omega -2)}{2\omega -2}\right])\hfill & \hfill \\ =\left[\frac{\omega -2}{2\omega -2}\right]M_1(G_X)+\left[4-\frac{4(\omega -2)}{2\omega -2}\right]2(m+n)\hfill & \hfill \\ \hspace{1em}+\left[m-4+\frac{4(\omega -2)}{2\omega -2}\right]n.\hfill & \hfill \end{array}$$

By simplifying, $$\omega M_1(G_X)\le +8\omega (m+n)+(2m-4)\omega n-2mn).$$

The equality in $c_u\le \frac{\omega -2}{2\omega -2}{(d_u-2)}^2+(d_u-1)+(d_u-2)$ holds for all $u\in V(G)$ if and only if $G[N[u]\setminus \{u\}]$ is a complete $\omega -1$ partite graph on $(d_u-2)$ vertices for all $u\in V(G)$ and the equality in $e_u\le m+d_u-1-c_u$ for all $u\in V(G)$ holds for $d_u>2$ if and only if either $V(G)\setminus \left\{u\right\}\subseteq N[u]$ or $G[V(G)\setminus N[u]]$ is a totally disconnected graph with $1\le \sigma \le n$. Therefore, the equality holds in the above theorem, if and only if $G_X$ is a complete $\omega$-partite graph with a self-loop on each vertex. ▪

Corollary 1.

Let $G_X$ be the graph obtained from a triangle-free graph G by attaching a self-loop at each vertex of $X\subseteq V(G)$, then $$M_1(G_X)\le 8m+(m+4)n,$$with equality if and only if $G_X$ is a complete bipartite graph with self-loop on each vertices.

4 Lower bounds

Lower bounds on $M_1(G_X)$ are discussed in this section.

Theorem 12.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$, with $\left|X\right|=\sigma$. Then $$M_1(G_X)\ge \frac{4{(m+\sigma )}^2}{n},$$with equality if and only if $G_X$ is a regular graph.

Proof.

For a sequence of real numbers ${\left\{a_i\right\}}_{1\le i\le n}$, we have $$\frac{\sum _{i=1}^n{a}_i^2}{n}\ge {\left(\frac{\sum _{i=1}^n{a}_i}{n}\right)}^2$$with equality if and only if all $a_i$, for $i=1,2,\dots ,n$ are equal.

By substituting $a_i=d_i,$ for $i=1,2,\dots ,n$, where $d_i$ is the degree of the vertex $v_i$ in the graph $G_X$, we get the desired inequality and the equality follows. ▪

Corollary 2.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$, with $\left|X\right|=\sigma$. Then $$\begin{array}{c}{M}_1(G_X)+M_1(\overline{G_X})\\ \hspace{1em}\ge \frac{1}{n}\left[n^2{(n+1)}^2+4(m+\sigma )(2(m+\sigma )-n(n+1))\right]\end{array}$$with equality if and only if $G_X$ is a regular graph.

Proof.

From Theorem 12, we have $$M_1(\overline{G_X})\ge \frac{1}{n}{(n(n+1)-2(m+\sigma ))}^2$$and the equality if and only if $\overline{G_X}$ is a regular graph, which is possible if and only if $G_X$ is regular. ▪

Theorem 13.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G),$ with $\left|X\right|=\sigma$. If $\Delta$ is the maximum degree of the graph $G_X$, then, $$M_1(G_X)\ge \frac{1}{n-1}[4(m+\sigma )(m+\sigma -\Delta )+n{\Delta }^2]$$with equality if and only if $G_X$ is a regular graph or a bi-regular graph with exactly one vertex having degree equal to $\Delta$.

Proof.

Let $\Delta =d_1\ge d_2\ge \cdots \ge d_n\ge 0$ be the degree sequence of the graph $G_X$. Then we have, $${\left(\frac{\sum _{i=2}^n{d}_i}{n-1}\right)}^2\le \frac{1}{n-1}\sum _{i=2}^n{d}_i^2$$with equality if and only if all $d_i^{\prime }s$ are equal for $2\le i\le n$. On adding ${\Delta }^2$ term on both sides and by simplifying we get the required inequality and the equality follows directly. ▪

Theorem 14.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$ and $\left|X\right|=\sigma$. If $\delta$ and $\Delta$ respectively the minimum and maximum degree in the graph $G_X$, then $$\begin{array}{c}{M}_1(G_X)\ge \frac{1}{n-2}\\ \hspace{1em}\left[4(m+\sigma )[m+\sigma -\delta -\Delta ]+{(\delta +\Delta )}^2\right]+{\Delta }^2+{\delta }^2\end{array}$$with equality if and only if $G_X$ is a

• regular graph or

• a bi-regular graph, where exactly one vertex has degree equal to $\delta$ (or $\Delta )$ or

• a tri-regular graph, where exactly two vertices are of degree equal to $\delta$ and $\Delta$.

Proof.

The proof is similar to the proof of Theorem 13. ▪

Theorem 15.

Let $G_X$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$. Let ${\lambda }_1(G_X)$ be the spectral radius (of adjacency matrix) of the graph $G_X$. Then, $$M_1(G_X)\ge {\lambda }_1^2(G_X).$$

Proof.

Let $x_i$ be the ith entry of a normalized eigenvector x of the adjacency matrix, $A(G_X)$ of the graph $G_X$ which corresponds to the largest eigenvalue (in absolute values), ${\lambda }_1(G_X)$ and let $A_i(G_X)$ be the ith row of $A(G_X)$. Then, $$\begin{array}{cc}|{\lambda }_1(G_X)x_i{|}^2={\lambda }_1^2(G_X)x_i^2\hfill & =|A_i(G_X)x{|}^2\hfill \\ \le |A_i(G_X){|}^2.\hfill & \hfill \end{array}$$

Now on taking the sum from $i=1$ to n, we get $${\lambda }_1^2(G_X)\le \sum _{i=1}^n|A_i(G_X){|}^2\le \sum _{i=1}^n{d}_i^2=M_1(G_X).$$

Theorem 16.

Let $G_X\ne n{K}_1$ be a graph obtained from a simple graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$ with $\left|X\right|=\sigma$. Let ${\lambda }_1$ and $E(G_X)$ respectively be the spectral radius and energy (of adjacency matrix) of the graph $G_X$. Then, $$M_1(G_X)\ge \frac{{\lambda }_1}{n^2}\left[{(E(G_X))}^2+{\sigma }^2\right].$$

Proof.

We have, $$\begin{array}{cc}0\le \sum _{i=1}^n\sum _{j=1}^n{\left(\left|{\lambda }_i-\frac{\sigma }{n}\right|-\left|{\lambda }_j-\frac{\sigma }{n}\right|\right)}^2\hfill & \hfill \\ =n\sum _{i=1}^n{\left|{\lambda }_i-\frac{\sigma }{n}\right|}^2+n\sum _{j=1}^n{\left|{\lambda }_j-\frac{\sigma }{n}\right|}^2-2{(E(G_X))}^2\hfill & \hfill \\ =2n\left[2m+\sigma -\frac{{\sigma }^2}{n}\right]-2{(E(G_X))}^2\hfill & \hfill \end{array}$$ $$\begin{array}{cc}\le 2n\left[n{\lambda }_1-\frac{{\sigma }^2}{n}\right]-2{(E(G_X))}^2\hfill & (\text{By Theorem} 5)\hfill \\ \le 2n\left[\frac{n{M}_1(G_X)}{{\lambda }_1}-\frac{{\sigma }^2}{n}\right]-2{(E(G_X))}^2.(\text{By Theorem} 15)\hfill & \hfill \end{array}$$

Theorem 17.

Let $G_X$ be a graph obtained from a simple connected graph G of order n and size m by attaching a self-loop at each vertex of $X\subseteq V(G)$, with $\left|X\right|=\sigma$. If $\overline{G_X}$ is also connected, then $$\begin{array}{c}{M}_1(G_X)+M_1(\overline{G_X})\\ \hspace{1em}\ge \{\begin{array}{cc}\frac{n{(n+1)}^2}{2},\hfill & \text{ if }n\text{ is odd and }\frac{n+1}{2}\text{ is even }\hfill \\ \frac{n{(n+1)}^2}{2}+2,\hfill & \text{ if }n\text{ is odd and }\frac{n+1}{2}\text{ is odd }\hfill \\ \frac{n}{2}+\frac{n{(n+1)}^2}{2},\hfill & \text{ if }n\text{ is even }\hfill \end{array}\end{array}$$with equality if and only if $G_X$ is $$\begin{array}{c}\{\begin{array}{c}\text{a regular graph with regularity }\frac{n+1}{2},\text{if n is odd}\hfill \\ \text{ and }\frac{n+1}{2}\text{ is even}\hfill \\ \text{a bi-regular graph with degree of }(n-1)\text{ vertices }\hspace{1em}\text{if n is odd}\hfill \\ \text{equal to }\frac{n+1}{2}\text{ and one vertex is of degree either and }\frac{n+1}{2}\text{ is odd}\hfill \\ \text{equal to }\frac{n-1}{2}\text{ or }\frac{n+3}{2},\hfill \\ \text{ a bi-regular graph with degree either}\hfill \\ \text{equal to }\frac{n+2}{2}\text{ or }\frac{n}{2},\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{if }n\text{ is even}.\hfill \end{array}\hfill \end{array}$$

Proof.

By Theorem 9, we have $M_1(G_X)+M_1(\overline{G_X})$ is minimum, if

$\sum _{u\in V(G)}d(u)(n+1-d(u))$ is maximum. The term, $d(u)(n+1-d(u))$ attains the maximum value, if $d(u)$ and $n+1-d(u)$ are nearly equal.

$\mathit{Case}1:$ When n is odd and $\frac{n+1}{2}$ is even, $d(u)(n+1-d(u))$ attains the maximum value if and only if $d(u)=\frac{n+1}{2}$, for every $u\in V(G)$. The maximum value of $M_1(G_X)+M_1(\overline{G_X})$ is equal to $$n{(n+1)}^2-2n{\left(\frac{n+1}{2}\right)}^2=\frac{n{(n+1)}^2}{2}.$$

$\mathit{Case}2:$ When n is odd and $\frac{n+1}{2}$ is odd, $d(u)(n+1-d(u))$ attains the maximum value if and only if $d(u)=\frac{n+1}{2}$ for $n-1$ vertices and $d(u)=\frac{n-1}{2}$ or $d(u)=\frac{n+3}{2}$. The maximum value of $M_1(G_X)+M_1(\overline{G_X})$ is equal to $$\begin{array}{c}n{(n+1)}^2-2\left[(n-1){\left(\frac{n+1}{2}\right)}^2+\left(\frac{n+3}{2}\right)\left(\frac{n-1}{2}\right)\right]\\ \hspace{1em}=\frac{n{(n+1)}^2}{2}+2.\end{array}$$

$\mathit{Case}3:$ When n is even, $d(u)(n+1-d(u))$ attains the maximum value if and only if $d(u)$ is equal to either $\lceil \frac{n+1}{2}\rceil =\frac{n+2}{2}$ or $\lfloor \frac{n+1}{2}\rfloor =\frac{n}{2}$, for every $u\in V(G)$. In both the cases, $d(u)(n+1-d(u))=\left(\frac{n+2}{2}\right)\left(\frac{n}{2}\right)$ and the minimum value of $M_1(G_X)+M_1(\overline{G_X})$ is equal to $$n{(n+1)}^2-2n\left(\frac{n+2}{2}\right)\left(\frac{n}{2}\right)=\frac{n}{2}+\frac{n{(n+1)}^2}{2}.$$

Hence the graph $G_X$ must be a bi-regular graph where degree of each vertex is either equal to $\frac{n}{2}$ or $\frac{n+2}{2}.$ ▪

Acknowledgments

We sincerely appreciate the reviewers for all the valuable comments and suggestions, which helped us to improve the quality of the manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).