The Differential on Graph Operator Q(G)

Abstract

If $G=\left(V\right(G),E(G\left)\right)$ is a simple connected graph with the vertex set $V\left(G\right)$ and the edge set $E\left(G\right)$, S is a subset of $V\left(G\right)$, and let $B\left(S\right)$ be the set of neighbors of S in $V\left(G\right)\setminus S$. Then, the differential of S$\partial \left(S\right)$ is defined as $\left|B\right(S\left)\right|-\left|S\right|$. The differential of G, denoted by $\partial \left(G\right)$, is the maximum value of $\partial \left(S\right)$ for all subsets $S\subseteq V\left(G\right)$. The graph operator $\mathrm{Q}\left(G\right)$ is defined as the graph that results by subdividing every edge of G once and joining pairs of these new vertices iff their corresponding edges are incident in G. In this paper, we study the relations between $\partial \left(G\right)$ and $\partial \left(\mathrm{Q}\left(G\right)\right)$. Besides, we exhibit some results relating the differential $\partial \left(G\right)$ and well-known graph invariants, such as the domination number, the independence number, and the vertex-cover number.

1. Introduction

Some social networks arising from technologies such as Whatsapp, Facebook, Twitter, etc., have served as useful tools for communication and dissemination of information. Due to the high popularity of these technologies, they now have a wide variety of applications in the marketing of many products. With these facts in mind, several authors [1,2] have established some influential maximization problems, which share an algorithmic problem for information diffusion in social networks: the problem of determining the best set of nodes to influence the rest. For example, in [1], the authors attacked this problem by means of submodular functions and provided an algorithm that produced a solution that was provably within 63% of optimal for certain instances. Two years later, the same group of researchers [2] developed a more general framework and showed that the mentioned maximization problem can be approximated in a more general model known as the decreasing cascade model. In [3], it was explained how the differential of a graph G could be motivated by these scenarios.

The study of the differential together with several other variants started in [4]. In particular, in [4], some bounds were established for $\partial \left(G\right)$. In that paper, the differential of G was related to the following maximization problem:

“You are allowed to buy as many tokens as you like, say k tokens, at cost of $1 each. You then place the tokens on some subset of k vertices of G. For each vertex of G which has no token on it, but is adjacent to a vertex with a token on it, you receive $1. Your objective is to maximize your profit, that is, the total value received minus the cost of the tokens bought.“

The differential $\partial \left(G\right)$ of a graph was also analyzed in [3,5,6,7,8,9,10,11,12,13]. In [10], it was established that $\partial \left(G\right)+{\gamma }_R\left(G\right)=n$, where n denotes the order of G and ${\gamma }_R\left(G\right)$ denotes the Roman domination number of G. These graph parameters lead to two natural algorithmic decision problems:

• DIF: If G is a graph and k is an integer, decide if $\partial \left(G\right)\ge k$;
• ROM: If G is a graph and l is an integer, decide if ${\gamma }_R\left(G\right)\le l$.

Due to the relation that these parameters satisfy, an algorithm for DIF can be used to decide the ROM and vice versa. In [8], it was proven that DIF is NP-complete by a reduction from the three-dimensional matching problem.

Most of the contributions reported in [3,5,6,7,8,9,10,11,12,13] lied on at least one of the following issues of the differential of a graph:

• To obtain inequalities relating the differential of G with other graph invariants of G.
• To study the differential $\partial \left(G\right)$ for the most important graph families (complete graphs, trees, star graphs, etc.).
• To study the variation of the differential $\partial \left(G\right)$ under certain transformations (graph operators, products of graphs, etc.).
• To determine the computational complexity of the DIF problem.

We remark that, until now, the understanding of the differential of a graph has been relatively modest, and hence, the study of each of these four issues can lead to deep and fascinating problems for future research.

The differential of $D\subseteq V\left(G\right)$ was also analyzed in [14], and the minimum differential of an independent set was studied in [15]. The B-differential or enclaveless number $\psi \left(G\right)$ of G is $max\left\{\right|B\left(D\right)|:D\subseteq V(G\left)\right\}$ and was treated in [16,17].

In this paper, G denotes a simple graph with vertex set $V\left(G\right)$, edge set $E\left(G\right)$, and $n:=\left|V\right(G\left)\right|\ge 3$. Let $u,v$ be two vertices of G, and let $S\subseteq V\left(G\right)$. As usual, $N_G\left(v\right)$ is the set of neighbors that v has in $V\left(G\right)$, and $N_G\left[v\right]$ denotes the closed neighborhood of v, i.e., $N_G\left[v\right]:=N_G\left(v\right)\cup \left\{v\right\}$. We denote by ${\delta }_G\left(v\right):=\left|N_G\left(v\right)\right|$ the degree of v in G and by $\delta \left(G\right)$ and $\mathrm{\Delta }\left(G\right)$ the minimum and the maximum degree of G, respectively. The subgraph of G induced by S is denoted by $G\left[S\right]$, and $\overline{S}:=V\left(G\right)\setminus S$. Then, $N_{\overline{S}}\left(v\right)$ consists precisely of the neighbors that v has in $\overline{S}$. Let $N_G\left(S\right):={\bigcup }_{v\in S}{N}_G\left(v\right)$ and $N_G\left[S\right]:=N_G\left(S\right)\cup S$. For $v\in S$, an external private neighbor of v with respect to S is a vertex $w\in N_G\left(v\right)\cap \overline{S}$, which satisfies that $w\notin N_G\left(u\right)$ for any $u\in S\setminus \left\{v\right\}$. The set of external private neighbors of v with respect to S is denoted by epn${}_G[v,S]$. Let $B_G\left(S\right)$ be the set of elements of $\overline{S}$ that have a neighbor in S, and let $C_G\left(S\right):=\overline{S\cup B_G\left(S\right)}$. Note that $\{S,B_G\left(S\right),C_G\left(S\right)\}$ is a partition of $V\left(G\right)$. The differential of $S\subseteq V\left(G\right)$ is defined as ${\partial }_G\left(S\right)=|B_G\left(S\right)|-|S|$, and the differential of G is defined as $\partial \left(G\right)=max\{{\partial }_G\left(S\right):S\subseteq V\left(G\right)\}$. We will say that S is a differential set if ${\partial }_G\left(S\right)=\partial \left(G\right)$. A differential set is a minimum (maximum) differential set if it has minimum (maximum) cardinality among all differential sets.

As long as no confusion can arise from the context, we often omit the reference to G in ${\delta }_G\left(v\right),N_G\left(v\right),N_G\left[v\right],$ etc.

Notice that if G is disconnected and $G_1,\dots ,G_k$ are its connected components, then $\partial \left(G\right)=\partial \left(G_1\right)+\cdots +\partial \left(G_k\right)$. Then, we shall assume that any graph under consideration is connected.

A graph operator is a function $F:\Gamma \to {\Gamma }^{\prime }$, where $\Gamma$ and ${\Gamma }^{\prime }$ are two families of graphs. The study of how a graph invariant changes when a graph operator is applied is a classical problem in graph theory. We recall that the line graph $L\left(G\right)$ of the graph G is the graph with vertex set on $E\left(G\right)$ in which $e,f\in E\left(G\right)$ are adjacent in $L\left(G\right)$ iff e and f are incident in G.

In [18], the subdivision graph $S\left(G\right)$ of G as the graph constructed from G by subdividing every edge of G once was defined. The graph $\mathrm{Q}\left(G\right)$ (following the notations [18]) is obtained from G by subdividing each edge of G once and joining pairs of these new vertices iff their corresponding edges have a common endvertex in G (see Figure 1). Then, $\mathrm{Q}\left(G\right)$ contains both $L\left(G\right)$ and $S\left(G\right)$ as proper induced subgraphs.

For $e=uv\in E\left(G\right)$, let $V\left(e\right):=\{u,v\}$. Now, let us define:

$$E_E\left(G\right):=\{\{e_1,e_2\}:e_1,e_2\in E\left(G\right),e_1\ne e_2,|V\left(e_1\right)\cap V\left(e_2\right)|=1\},$$

and:

$$E_V\left(G\right):=\{\{e,u\}:e\in E\left(G\right),u\in V\left(e\right)\}.$$

Then, $\mathrm{Q}\left(G\right)=(V\left(G\right)\cup E\left(G\right),E_E\left(G\right)\cup E_V\left(G\right)).$

Remark 1.

From the last equality, it is clear that $V\left(\mathrm{Q}\left(G\right)\right)$ is the disjoint union of $V\left(G\right)$ and $E\left(G\right)$. For brevity, we shall use $V:=V\left(G\right)$ and $L:=E\left(G\right)$. Then, trivially, $\left|V\right|=\left|V\right(G\left)\right|$, $\left|L\right|=\left|E\right(G\left)\right|$. We also note that all vertices $u\in L\cap V\left(\mathrm{Q}\left(G\right)\right)$ have exactly two neighbors in $V\cap V\left(\mathrm{Q}\left(G\right)\right)$. See Figure 1.

From now on, we assume that V and L are the proper subsets of $V\left(\mathrm{Q}\left(G\right)\right)$ described in Remark 1.

The graphs provide a formal and natural language for modeling and studying several molecular phenomena in chemistry. A “topological index” is a graph invariant applicable in this kind of phenomena. Perhaps the best known topological indices are the Zagreb indices. They have been used to study molecular complexity, chirality, $ZE$-isomerism, hetero-systems, etc. As can be seen in [19,20,21,22], $L\left(G\right),S\left(G\right),\mathrm{Q}\left(G\right)$, and other related graph operators have been widely studied in the context of the topological indices. On the other hand, the theory of graph operators is a classical and active area of research in graph theory, which has the following general question as the prime motivation: Given a graph G, a graph parameter $\omega$, and a graph operator $O\left(G\right)$, what can we say about $\omega (O(G\left)\right)$ when certain information on G or on $\omega \left(G\right)$ is known? As can be seen in [23,24] and the references therein, at least one of $L\left(G\right),S\left(G\right),$ or $\mathrm{Q}\left(G\right)$ has been studied from this second point of view.

2. Results

We start by listing some basic properties of $\mathrm{Q}\left(G\right)$, which can be deduced easily from the definition of $\mathrm{Q}\left(G\right)$. We use $E_n$ to denote the graph of order $n\ge 2$ with no edges.

Proposition 1.

If G is a graph of order n, then:

(i) 

$\left|V\right(\mathrm{Q}\left(G\right)\left)\right|=\left|V\right|+\left|L\right|.$

(ii) 

$\left|E\right(\mathrm{Q}\left(G\right)\left)\right|=2\left|L\right|+\left|E\right(L\left(G\right)\left)\right|.$

(iii) 

$L\left(G\right)$ is an induced subgraph of $\mathrm{Q}\left(G\right).$

(iv) 

$G\cong \mathrm{Q}\left(G\right)$ if and only if $G\cong E_n$.

(v) 

If $v\in V$, then ${\delta }_{\mathrm{Q}\left(G\right)}\left(v\right)={\delta }_G\left(v\right)$.

(vi) 

If $u\in L$, then $\left|N\right(u)\cap V|=2$.

(vii) 

If $v\in V$ and $u\in N_{\mathrm{Q}\left(G\right)}\left(v\right)$, then $N_{\mathrm{Q}\left(G\right)}\left[v\right]\subseteq N_{\mathrm{Q}\left(G\right)}\left[u\right]$.

(viii) 

If $u\in L$, then there exist vertices $x,y\in V$ such that $\{x,y\}=N_{\mathrm{Q}\left(G\right)}\left(u\right)\cap V$ and ${\delta }_{\mathrm{Q}\left(G\right)}\left(u\right)={\delta }_G\left(x\right)+{\delta }_G\left(y\right)$.

(ix) 

If G is a regular graph, then $\mathrm{Q}\left(G\right)$ is a biregular graph.

We recall that a vertex cover of G is a subset $S\subseteq V\left(G\right)$ such that each edge of G has at least one endvertex in S. The vertex-covering number $\tau \left(G\right)$ of G is the size of any smallest vertex cover in G. A subset $S\subseteq V\left(G\right)$ is a dominating set of G if each vertex in G belongs to S or has a neighbor in S. The domination number $\gamma \left(G\right)$ of G is the minimum cardinality of a dominating set of G. Similarly, a subset $S\subseteq V\left(G\right)$ is independent if any two vertices in S are not adjacent in G. The independence number $\alpha \left(G\right)$ of G is the maximum cardinality of an independent set of G.

Proposition 2.

If G is a graph and S is a differential set of $\mathrm{Q}\left(G\right)$, then $S\subseteq L$.

Proof. 

Let $S\subseteq V\left(\mathrm{Q}\left(G\right)\right)$ be as in Proposition 2. Suppose that there is $v\in S\cap V$. If there exist $w\in N\left(v\right)\cap S$, then $\partial (S\setminus \{v\left\}\right)=\left|B\right(S\left)\right|+1-\left|S\right|+1=\partial \left(S\right)+2=\partial \left(\mathrm{Q}\left(G\right)\right)+2$, a contradiction. Let $u\in N\left(v\right)$ and $v^{\prime }\in N\left(u\right)\cap V$ with $v^{\prime }\ne v$. Let us show that $v^{\prime }\in B\left(S\right)$. If $v^{\prime }\in C\left(S\right)$, then $\partial \left(\right(S\setminus \left\{v\right\})\cup \{u\left\}\right)\ge \left|B\right(S\left)\right|+1-\left|S\right|=\partial \left(\mathrm{Q}\left(G\right)\right)+1$, a contradiction. If $v^{\prime }\in S$, then $\partial ((S\setminus \{v,v^{\prime }\})\cup \left\{u\right\})\ge |B\left(S\right)|+1-|S|+1=\partial \left(\mathrm{Q}\left(G\right)\right)+2$, again a contradiction. Therefore, $v^{\prime }\in B\left(S\right)$; hence, there exists $u^{\prime }\in N\left(v^{\prime }\right)$ such that $u^{\prime }\in S$; according to this and by the definition of $\mathrm{Q}\left(G\right)$, we know that $u\in N\left(u^{\prime }\right)$, and since u is arbitrary, we conclude $epn[v,S]=\varnothing$, a contradiction. Therefore, $S\cap V=\varnothing$. □

Proposition 3.

If G is a graph of order $n\ge 2$, then $\partial \left(\mathrm{Q}\left(G\right)\right)\ge \partial \left(L\left(G\right)\right)+2$.

Proof. 

Let S be a differential set of $L\left(G\right)$, and notice that $B_{L\left(G\right)}\left(S\right)\subseteq B_{\mathrm{Q}\left(G\right)}\left(S\right)$; even more, there exist $v_1,v_2\in B\left(S\right)\cap V$, then ${\partial }_{\mathrm{Q}\left(G\right)}\left(S\right)=|B_{\mathrm{Q}\left(G\right)}\left(S\right)|-|S|\ge |B_{L\left(G\right)}\left(S\right)|+2-|S|=\partial \left(L\left(G\right)\right)+2$. □

For the n star graph, equality holds in the above proposition. For an example, see Figure 2.

Proposition 4.

If G is a graph, then L contains a dominating set S of $\mathrm{Q}\left(G\right)$ such that $\gamma \left(\mathrm{Q}\left(G\right)\right)=\left|S\right|$.

Proof. 

Let D be a minimum dominating set of $\mathrm{Q}\left(G\right)$. If $D\subseteq L$, there is nothing to show, so we may assume that $D\cap V$ has at least one vertex v. We know that $N_{\mathrm{Q}\left(G\right)}\left[v\right]\subseteq N_{\mathrm{Q}\left(G\right)}\left[u\right]$ for any $u\in N_{\mathrm{Q}\left(G\right)}\left(v\right)$ by Proposition 1$\left(vii\right)$. Then, $D^{\prime }:=(D\setminus \left\{v\right\})\cup \left\{u\right\}$ is a minimum dominating set of $\mathrm{Q}\left(G\right)$ with $|D^{\prime }\cap V|=|D\cap V|-1$. Continuing in this way, we can construct the desired S. □

Proposition 5.

If G is a graph and S is a differential set of $\mathrm{Q}\left(G\right)$, then S is a dominating set of $L\left(G\right)$.

Proof. 

Suppose that S is a differential set of $\mathrm{Q}\left(G\right)$. By Proposition 2, we know that $S\subseteq L$. We recall that $\{S,B(S),C(S\left)\right\}$ is a partition of $V\left(\mathrm{Q}\left(G\right)\right)$. If S is a dominating set for $L\left(G\right)$, there is nothing to show, so we may assume that there exists a vertex $u\in C\left(S\right)\cap L$. Proposition 1 (viii) implies that $N\left(u\right)\cap V=\{v_1,v_2\}$ for some $v_1,v_2\in V$. If $v_i\in S$ for some $i\in \{1,2\}$, then $u\in B\left(S\right)$, a contradiction. If $v_i\in B\left(S\right)$ for some $i\in \{1,2\}$, then there exists $u^{\prime }\in S$ such that $v_i\in N\left(u^{\prime }\right)$ for some $i\in \{1,2\}$, and therefore, $u\in N\left(u^{\prime }\right)$. This implies $u\in B\left(S\right)$, a contradiction. We conclude that $v_1,v_2\in C\left(S\right)$, and so, $\partial (D\cup \{u\left\}\right)>\partial \left(D\right)=\partial \left(\mathrm{Q}\left(G\right)\right)$, which is a contradiction. □

Corollary 1.

If G is a graph and S is a differential set of $\mathrm{Q}\left(G\right)$, then $C\left(S\right)\subseteq V$.

Corollary 2.

If G is a graph and S is a differential set of $\mathrm{Q}\left(G\right)$, then $\left|S\right|\ge \gamma \left(L\left(G\right)\right)$.

Proposition 6.

If G is a graph of order n, then $\gamma \left(\mathrm{Q}\right(G\left)\right)\ge \lceil \frac{n}{2}\rceil$.

Proof. 

Suppose that D is a minimum dominating set of $\mathrm{Q}\left(G\right)$ and that $\left|D\right|<\lceil \frac{n}{2}\rceil$. By Proposition 2, we can assume that $D\subseteq L$. This and Proposition 1$vi)$ imply that D has at most $2\left|D\right|$ adjacent vertices in V. If n is even, then $2\left|D\right|\le 2\left(\frac{n}{2}\right)-1=n-1$; therefore, D is not a dominating set of $\mathrm{Q}\left(G\right)$, which is a contradiction. If $n=2k+1$ with $k\in \mathbb{N}$, then $2\left|D\right|\le 2\lceil \frac{n}{2}\rceil -2=2k=n-1$; therefore, D is not a dominating set in $\mathrm{Q}\left(G\right)$, a contradiction. □

Observation 1.

Note that for the cycle, complete, and path graphs, equality holds in the above proposition.

Proposition 7.

If G is a graph of order n, then G has a perfect matching iff $\gamma \left(\mathrm{Q}\right(G\left)\right)=\frac{n}{2}$.

Proof. 

According to Proposition 6, it suffices to show that $\gamma \left(\mathrm{Q}\left(G\right)\right)\le \frac{n}{2}$. Let $M:=\{e_1,...,e_k\}\subseteq E\left(G\right)$ be a perfect matching of G and $M^{\prime }:=\{u_1,...,u_k\}\subseteq L$ the vertex set in $\mathrm{Q}\left(G\right)$ corresponding to the edges of M. Let us prove that $M^{\prime }$ is a dominating set of $\mathrm{Q}\left(G\right)$. Let $v\in V$; since M is a perfect matching, there is $x\in V$ and $i\in \{1,\dots ,k\}$ such that $e_i=xv$. Hence, $v\in N\left(u_{e_i}\right)$. Let $u\in L\setminus M^{\prime }$; by Proposition 1 ($vi$), there are $v_1,v_2\in N\left(u\right)\cap V$ y $v_1{v}_2\in E\left(G\right)$. Since M is a perfect matching, there is $y\in V$ and $i\in \{1,\dots ,k\}$ such that $e_i=v_{1}y$, then $e_i$ is incident to $v_1{v}_2$, and hence, $u\in N\left(u_{e_i}\right)$ for some $i\in \{1,\dots ,k\}$. This shows that $M^{\prime }$ is a dominating set of $\mathrm{Q}\left(G\right)$, and so, $\gamma \left(\mathrm{Q}\left(G\right)\right)\le |M^{\prime }|=\frac{n}{2}$.

Conversely, assume that $\gamma \left(\mathrm{Q}\left(G\right)\right)=\frac{n}{2}$. Then, there is a minimum dominating set D of $Q\left(G\right)$ contained in L, by Proposition 4. Let $D^{\prime }=\{e_1,\dots ,e_{\frac{n}{2}}\}\subseteq E\left(G\right)$ be the set of edges of G, corresponding to the vertices of D. If $v\in V$, then there exist $u\in D$ such that $v\in N\left(u\right)$, and then, v is an endvertex of some edge in $D^{\prime }$. Let us prove that $D^{\prime }$ is an independent edge set. Assume that there are $i,j\in \{1,\dots ,\frac{n}{2}\}$ ($i\ne j$) and $x\in V$ such that $e_i=x{y}_1$ y $e_j=x{y}_2$ with $y_1,y_2\in V$, then $x\in N\left(u_i\right)\cap N\left(u_j\right)\cap V$, and by Proposition 1$\left(vi\right)$, we have that the maximum number of vertices in V adjacent to D is $2\left|D\right|-1\le n-1$, a contradiction. Therefore, G has a perfect matching. □

Let us define $m:=\left|V\right(\mathrm{Q}\left(G\right)\left)\right|$. It is well known that $\partial \left(\mathrm{Q}\left(G\right)\right)\le m-2$. Now, we will determine what G is, when $\partial \left(\mathrm{Q}\left(G\right)\right)\in \{m-3,m-2\}$. For this, we need to recall three known facts.

Proposition 8

([5]). If D is a differential set of a graph G, then $\left|D\right|\le \gamma \left(G\right)$.

Proposition 9

([11]). If G is a graph of order $n\ge 3$ and maximum degree Δ, then:

(a) 

$\mathrm{\Delta }=n-1$ iff $\partial \left(G\right)=n-2$.

(b) 

$\mathrm{\Delta }=n-2$ iff $\partial \left(G\right)=n-3$.

(c) 

If $\mathrm{\Delta }=n-3$, then $\partial \left(G\right)=n-4$.

Proposition 10.

If G is a simple graph of order n, then:

(a) 

$\partial \left(\mathrm{Q}\left(G\right)\right)=\left|V\right(\mathrm{Q}\left(G\right)\left)\right|-2$ iff $G=P_2$.

(b) 

$\partial \left(\mathrm{Q}\left(G\right)\right)=\left|V\right(\mathrm{Q}\left(G\right)\left)\right|-3$ iff $G\in \{P_3,K_3,E_1\uplus P_2\}$.

Proof. 

(a) Suppose that $\partial \left(\mathrm{Q}\left(G\right)\right)=\left|V\right(\mathrm{Q}\left(G\right)\left)\right|-2$. By Proposition 9 (a), we have that $\mathrm{\Delta }\left(\mathrm{Q}\left(G\right)\right)=\left|V\right(\mathrm{Q}\left(G\right)\left)\right|-1$, and so, $\gamma \left(\mathrm{Q}\left(G\right)\right)=1$. Then, Proposition 6 implies $n=2$, and consequently, $G\in \{E_2,P_2\}$. If $G=E_2$, then $\mathrm{Q}\left(G\right)=E_2$ and $\mathrm{\Delta }\left(\mathrm{Q}\left(E_2\right)\right)=1$, a contradiction; therefore $G=P_2$. The backward implication is easy to check. (b) Now, we suppose that $\partial \left(\mathrm{Q}\left(G\right)\right)=\left|V\right(\mathrm{Q}\left(G\right)\left)\right|-3$. By Proposition 9 (b), we have that $\mathrm{\Delta }\left(\mathrm{Q}\left(G\right)\right)=\left|V\right(\mathrm{Q}\left(G\right)\left)\right|-2$, and so, $\gamma \left(\mathrm{Q}\left(G\right)\right)=2$. Then, Proposition 6 implies that $n\in \{1,2,3,4\}$. It is not hard to derive a contradiction for each of the cases $n=1$ and $n=2$. Then, we can assume $n\in \{3,4\}$. If $n=4$, by Proposition 1 vi), we conclude $\mathrm{\Delta }\left(\mathrm{Q}\left(G\right)\right)<\left|V\right(\mathrm{Q}\left(G\right)\left)\right|-2$, a contradiction. If $n=3$, then $G\in \{E_3,P_3,K_3,E_1\uplus P_2\}$. Since $G=E_3$ does not satisfy the hypothesis, we are done. Again, the backward implication is easy to see. □

Theorem 1.

If G is a graph of order $n\ge 3$, then $\alpha \left(\mathrm{Q}\left(G\right)\right)=\left|V\right|$.

Proof. 

Since $x_1{x}_2\notin E\left(\mathrm{Q}\left(G\right)\right)$ for all $x_1,x_2\in V$, then V is an independent set of $\mathrm{Q}\left(G\right)$. Let $D\subseteq V\left(\mathrm{Q}\left(G\right)\right)$ be a maximum independent set of $\mathrm{Q}\left(G\right)$. We will show that $D\subseteq V$. Seeking a contradiction, suppose that there is $u\in D\cap L$. From Proposition 1$\left(vi\right)$, we know that there exist $v_1,v_2\in V$ such that $\{v_1,v_2\}=N\left(u\right)\cap V$. From this and the independence of D, it follows that $v_1,v_2\notin D$. Even more, $v_i\notin N\left(u^{\prime }\right)$ for all $i\in \{1,2\}$ and $u^{\prime }\in D\cap L$, otherwise $u\in N\left(u^{\prime }\right)$; this contradicts the independence of D. Therefore, $(D\setminus \left\{u\right\})\cup \{v_1,v_2\}$ is independent in $\mathrm{Q}\left(G\right)$, contradicting the maximality of D. Therefore, $D\subseteq V$, and by the maximality of D, we conclude that $D=V$. □

Observation 2.

[25] For any graph G, $\left|V\right(G\left)\right|=\alpha \left(G\right)+\tau \left(G\right)$.

Corollary 3.

If G is a graph, then $\tau \left(\mathrm{Q}\left(G\right)\right)=\left|L\right|$.

Corollary 4.

If G is a graph, then $\tau \left(\mathrm{Q}\left(G\right)\right)\ge \gamma \left(L\left(G\right)\right)$.

Observation 3.

If S is a differential set of $\mathrm{Q}\left(G\right)$, $n_1:=|B\left(S\right)\cap V|$, and $n_2:=|B\left(S\right)\cap L|$, then $\left|B\left(S\right)\right|=n_1+n_2,\left|V\right|=\left|C\left(S\right)\right|+n_1,$ and $\left|L\right|=\left|S\right|+n_2$.

Proposition 11.

If G is a graph and S is a minimum differential set of $\mathrm{Q}\left(G\right)$, then $n_1=2\left|S\right|$.

Proof. 

Suppose that S is a minimum differential set of $\mathrm{Q}\left(G\right)$. By Proposition 2, we know that $S\subseteq L$. If $\left|S\right|=1$, by the definition of $\mathrm{Q}\left(G\right)$, the equality holds. Thus, we can assume that S has at least two vertices, say $u_1$ and $u_2$.

Now, suppose that $u_1$ and $u_2$ are adjacent in $\mathrm{Q}\left(G\right)$. Then, there exist $v_1,v_2,v_3\in V$ such that $\{v_1,v_2\}=N\left(u_1\right)\cap V$ and $\{v_2,v_3\}=N\left(u_2\right)\cap V$. Since S is a minimum differential set, then |epn$[u,S]|\ge 2$ for all $u\in S$. This and the fact $\left|N\right(u_i)\cap V|=2$ for all $i=1,2$ imply the existence of an $x_2\in$ epn$[u_2,S]\cap L$. Since $x_2\in L$, then $x_2$ has exactly two neighbors in V, say $y_1$ and $y_2$.

If $x_2$ is adjacent to some of $v_1$ or $v_2$, then $x_2\in N\left(u_1\right)$, contradicting that $x_2$ is a private neighbor of $u_2$. Then, we conclude that $x_2\in N\left(u_2\right)$ and that $y_i=v_3$ for some $i\in \{1,2\}$. Without loss of generality, we can assume $y_1=v_3$. Therefore, $y_2\ne v_i$ for all $i\in \{1,2,3\}$. Since $x_2\in$ epn$[u_2,S]$, then $y_2\in B\left(S\right)\cup C\left(S\right)$. If $y_2\in B\left(S\right)$, then there exists $u\in S\setminus \{u_1,u_2\}$ such that $y_2\in N\left(u\right)$, and so, $x_2\in N\left(u\right)$, contradicting that $x_2$ is a private neighbor of $u_2$. Thus, we can assume that $y_2\in C\left(S\right)$. From the latter, we get $\partial ((S\setminus \left\{u_2\right\})\cup \left\{x_2\right\})=\left(\right|B\left(S\right)|-1+1+1)-\left(\right|S|-1+1)=\partial \left(S\right)+1$, a contradiction. This last contradiction implies that S is independent in $\mathrm{Q}\left(G\right)$. The latter and $S\subseteq L$ imply that $\left|B\right(S)\cap V|=2\left|S\right|$, as required. □

Corollary 5.

If G is a graph of order n and S is a minimum differential set in $\mathrm{Q}\left(G\right)$, then $\left|V\right|=2\left|S\right|+\left|C\right(S\left)\right|$.

Theorem 2.

If G is a graph of order n, then $\partial \left(\mathrm{Q}\left(G\right)\right)=\tau \left(\mathrm{Q}\left(G\right)\right)$.

Proof. 

Suppose that S is a minimum differential set of $\mathrm{Q}\left(G\right)$. Then:

$$\begin{array}{ccc}\partial \left(\mathrm{Q}\left(G\right)\right)\hfill & =\hfill & \partial \left(S\right)=\left|B\right(S\left)\right|-\left|S\right|\hfill \\ \hfill & =\hfill & n_1+n_2-\left|S\right|\hfill \\ \hfill & =\hfill & \left(\right|V|-|C\left(S\right)\left|\right)+\left(\right|L|-|S\left|\right)-\left|S\right|\hfill \\ \hfill & =\hfill & \left|V\right|+\left|L\right|-\left|C\right(S\left)\right|-2\left|S\right|\hfill \\ \hfill & =\hfill & \left|L\right|\hfill \\ \hfill & =\hfill & \tau \left(\mathrm{Q}\left(G\right)\right)\hfill \end{array}$$

 □

Corollary 6.

Let $K_n,S_n,S_{m,n},K_{m,n},P_n,C_n,W_n,T$ be the complete, star, double star, complete bipartite, path, cycle, wheel, and tree graphs, respectively, then the following hold:

(i) 

$\partial \left(\mathrm{Q}\left(K_n\right)\right)={\displaystyle \frac{n(n-1)}{2}}$.

(ii) 

$\partial \left(\mathrm{Q}\left(S_n\right)\right)=n-1$.

(iii) 

$\partial \left(\mathrm{Q}\left(S_{m,n}\right)\right)=n+m-1$.

(iv) 

$\partial \left(\mathrm{Q}\left(K_{m,n}\right)\right)=mn$.

(v) 

$\partial \left(\mathrm{Q}\left(P_n\right)\right)=n-1$.

(vi) 

$\partial \left(\mathrm{Q}\left(C_n\right)\right)=n$.

(vii) 

$\partial \left(\mathrm{Q}\left(W_n\right)\right)=2(n-1)$.

(viii) 

$\partial \left(\mathrm{Q}\left(T\right)\right)=n-1$.

Proof. 

Theorem 2 implies $\partial \left(\mathrm{Q}\left(G\right)\right)=\tau \left(\mathrm{Q}\left(G\right)\right)$, and Corollary 3 implies $\tau \left(\mathrm{Q}\left(G\right)\right)=\left|L\right|=\left|E\right(G\left)\right|$. On the other hand, note that the expression on the right side of each equation is precisely the number of edges of the corresponding graph $G\in \{K_n,S_n,S_{m,n},K_{m,n},P_n,C_n,W_n,T\}$. Clearly, each of the claimed equalities follows directly from these three facts. □

3. Concluding Remarks

If G is a simple graph, then $\mathrm{Q}\left(G\right)$ denotes the graph on $V\left(G\right)\cup E\left(G\right)$ in which two distinct elements of $V\left(G\right)\cup E\left(G\right)$ are adjacent as vertices of $\mathrm{Q}\left(G\right)$ iff they are adjacent or incident in G. The graph operator $\mathrm{Q}\left(G\right)$ belongs to an extensive collection of graph operators that have been widely studied in graph theory for a long time. Perhaps the better known member of that collection is the line graph $L\left(G\right)$ of G. A simple inspection of graphs $\mathrm{Q}\left(G\right)$ and $L\left(G\right)$ reveals that $L\left(G\right)$ is contained in $\mathrm{Q}\left(G\right)$ as the induced subgraph.

In this work, we determined the exact value of three graph theoretical parameters for $\mathrm{Q}\left(G\right)$, namely the differential $\partial \left(\mathrm{Q}\left(G\right)\right)$, the vertex-covering number $\tau \left(\mathrm{Q}\left(G\right)\right)$, and the independence number $\alpha \left(\mathrm{Q}\left(G\right)\right)$. We also provided a tight lower bound for the domination number $\gamma \left(\mathrm{Q}\left(G\right)\right)$ of $\mathrm{Q}\left(G\right)$.

Surprisingly, we discovered that $\partial \left(\mathrm{Q}\left(G\right)\right)$ is equal to $\tau \left(\mathrm{Q}\left(G\right)\right)$ and that the latter is exactly the number of edges of G. As a consequence, we managed to give explicit expressions for $\partial \left(\mathrm{Q}\left(G\right)\right)$, when G belongs to some fundamental graphs, such as complete graphs, trees, etc.

The graph parameters $\partial ,\tau ,\alpha$, and $\gamma$ are of quite independent interest in graph theory. For instance, it is well known that the exact determination of each of them is computationally hard for most of the graphs. However, as can be seen throughout this work, it seems that the structure of $\mathrm{Q}\left(G\right)$ and the concept of the differential of a graph have enabled establishing some interesting relationships between these parameters and some of the invariants of $\mathrm{Q}\left(G\right)$.

In the Introduction, we already mentioned several interesting general problems involving the differential of a graph. In particular, we mentioned that the decision problem DIF is NP-complete. On the other hand, here, we showed that $\partial \left(\mathrm{Q}\left(G\right)\right)=\left|E\right(G\left)\right|$, and so, given a graph G and an integer k, we can decide whether $\partial \left(\mathrm{Q}\left(G\right)\right)\ge k$ in polynomial time. Motivated by this fact, we propose the following question: Which graph operators maintain the decision problem DIF in the NP-complete class?