Graph invariants, often regarded as topological indices, play a pivotal role in understanding and quantifying the structural properties of graphs. Among these, the line completion number has emerged as a significant measure of a graph’s edge connectivity and topology. In 1992, Bagga et al. defined a generalization of line graphs, namely super line graphs, and introduced the concept of the line completion number as a topological index of a graph. They calculated the line completion number for several classes of graphs, showcasing its utility in understanding graph structure. The line completion number of a graph, is the smallest index such that the super line graph becomes a complete graph. This index encapsulates the interplay between edge relationships and structural complexity, making it a versatile tool for characterizing graphs. Building upon this foundation, we analogously introduce the concepts of super point graphs and the point completion number, as vertex-centric topological indices. We establish a relationship between the point completion number and the line completion number, further extending the framework of graph invariants. Additionally, we compute the point completion numbers for various graph classes and analyze their structural implications. Our findings emphasize the significance of completion numbers as robust descriptors for graph topology, with potential applications in network analysis, chemistry, and other domains.
We consider simple, undirected, finite graphs without multiple edges. A graph \(G\) is defined by its vertex set \(V(G)\) and edge set \(E(G)\). Standard graph-theoretic terminology used here is as detailed in [12].
The super line graph of index \(r\), denoted \(\mathscr L_r(G)\) is a generalization of the classical line graph, where the vertices of \(\mathscr L_r(G)\) represent sets of \(r\)-edges of \(G.\) Two vertices in \(\mathscr L_r(G)\) are adjacent if there is an edge in one set adjacent to an edge in the other set. When \(r=1,\) \(\mathscr L_r(G)\) coincides with the line graph of \(G.\) The line completion number, denoted \(lc(G)\) is the smallest index \(r\) such that \(\mathscr L_r(G)\) becomes a complete graph. As a topological index, \(lc(G)\) reflects the extent to which edge relationships can be captured through increasing levels of connectivity in \(\mathscr L_r(G)\). For example, low values of \(lc(G)\) indicate high initial edge density or strong connectivity; whereas high values of \(lc(G)\) suggest sparse connectivity or more complex structures.
The line completion number has been extensively studied for various graph classes:
Bagga, Beineke, and Varma [8, 9] introduced and studied the super line graph and its properties [1, 2, 3, 4, 5, 7, 10].
Specific results on \(lc(G)\) for hypercubes [14], grid graphs [13] and other graph classes have enriched its understanding.
Bagga et al. [6] have tried to determine the the line completion numbers of complete bipartite graphs \(K_{m,n}\), where \(m\) is fixed and \(m\leq n\) for different cases of \(m\) and \(n.\)
We extend the concept of the super line graph to super point graphs, where the focus shifts from edge sets to vertex sets. The super point graph of index \(r\), denoted \(\mathscr P_r(G)\), considers \(r\)-vertex subsets of \(G\) as its vertices, with adjacency defined analogously to \(\mathscr L_r(G)\). The point completion number, \(pc(G)\) is the smallest index \(r\) such that \(\mathscr P_r(G)\) becomes a complete graph. As a topological index, \(pc(G)\) captures vertex-centric connectivity and complements the edge-focused line completion number.
In this paper, we explore the line completion number from a topological perspective, connecting it to broader graph properties. We also introduce the analogous concepts of super point graphs and point completion numbers, extending the idea of topological indices to vertices. Additionally, we establish relationships between these indices and other structural invariants such as the independence number and graph powers.
We first discuss about powers of graphs.
Definition 2.1. The \(k^{th}\) power \(G^k\) of a graph \(G\) is another graph that has the same set of vertices, but in which two vertices are adjacent if their shortest path distance in \(G\) is at most \(k.\)
Graph powers often serve as tools to study connectivity and relationships between graph invariants. In Figure 1, we indicates the graph powers.
Following is the definition of an independent set and the independence number of a graph.
Definition 2.2. A set \(S\) of vertices is independent if any two vertices of \(S\) are non-adjacent. The vertex independence number or simply the independence number, of a graph \(G,\) denoted by \(\alpha (G)=\max\left\lbrace \lvert S \rvert \bigm | S \text{ is independent set of vertices in }G\right\rbrace\).
In [11], Hales gave the independence number of the strong product \(C_m\otimes C_n\) of odd cycles and of higher (strong) power \(C_m^k\) of certain odd cycles \(C_m.\) In particular, \[\alpha (P_n^k)= \displaystyle \left\{\begin{array}{rcl}\displaystyle \left\lceil\frac{n}{k+1}\right\rceil & \mbox{if} & k<n,\\ 1\hspace{.8cm} & \mbox{if} & k\geq n \end{array}\right.\] and \[\alpha (C_n^k)= \displaystyle \left\{\begin{array}{rcl}\displaystyle \left\lfloor\frac{n}{k+1}\right\rfloor & \mbox{if} & 1+2k<n,\\ 1\hspace{.8cm} & \mbox{if} & 1+2k\geq n. \end{array}\right.\]
Independence number of some graph powers are given in Figure 2.
We now give the definition of a super point graph.
Definition 2.3. Let \(G\) be a graph with \(n\) vertices and let \(r\) be a positive integer. Then the super point graph \(\mathscr P_r(G)\) of \(G\) with index \(r\leq n\) is a graph such that its vertices are all possible r-subsets of the vertex set of \(G,\) and two vertices \(X\) and \(Y\) are adjacent if some vertex from \(X\) is adjacent to some vertex from \(Y\) in \(G.\)
In general, the number of vertices of \(\mathscr P_r(G)\) is \(\binom{n}{r}.\) In figures, we use the simpler notation \(ab\) for the vertex \(\{a,b\}\) in \(\mathscr P_2(G), ~abc\) for the vertex \(\{a,b,c\}\) in \(\mathscr P_3(G),\) and so on.
The following result lists some basic properties of \(\mathscr P_r(G).\)
Lemma 2.4. (1) Super point graph of index \(1\) is isomorphic to the graph itself, i.e., \(\mathscr P_1(G)\cong G\).
(2) For any two non-adjacent vertices \(X\) and \(Y\) in \(\mathscr P_r(G),\) \(X\cap Y\) is either empty or a set of independent vertices, no vertex in \(X\) is adjacent to any vertex in \(Y-X,\) and no vertex in \(Y\) is adjacent to any vertex in \(X-Y.\)
Proof. Proof of (1) and (2) follow immediately from the definition of the super point graph. ◻
The next lemma is useful for our next theorem.
Lemma 2.5. [10] Let \(S\) be a set of \(m\) elements and let \(r < \frac{m}{2}.\) Then there exists a one-to-one mapping \(\phi\) from the set of \(r\)-subsets of \(M\) into the set of \((r+1)\)-subsets of \(M\) such that for each \(r\)-subset \(X,~ X\subseteq \phi (X).\)
Theorem 2.6. (1) If \(H\) is a subgraph of a graph \(G\), then \(\mathscr P _r(H)\) is an induced subgraph of \(\mathscr P _r(G),\) where \(1\leq r\leq\) \(\mid V(H)\mid.\)
(2) For \(1 \leq r < \frac{p}{2},~\mathscr P_r(G)\) is isomorphic to a subgraph of \(\mathscr P_{r+1}(G),\) where \(p=\mid V(G)\mid.\)
Proof. (1) This follows from the observation that \(V(H)\subseteq V(G),\) and two \(r\)-set of \(V(H)\) are adjacent in \(\mathscr P _r(H)\) if and only if they are adjacent in \(\mathscr P _r(G).\)
(2) By the lemma 2.5, there is a one-to-one mapping from \(V( \mathscr P _r(G))\) into \(V( \mathscr P _{r+1}(G))\) with each r-set of \(V(G)\) being mapped to a set containing it. If two r-sets are adjacent in \(\mathscr P _r(G)\), then their images are also adjacent in \(\mathscr P _{r+1}(G)\). Hence, the result. ◻
Proposition 2.7. A graph \(G\) is a subgraph of super point graph \(\mathscr P_r(G),\) where \(1\leq r<\mid V(G)\mid .\)
Proof. The proof follows by definition of the super point graph. ◻
Let us consider some graphs and their super point graphs. In the following Figure 3, we have drawn the super point graphs of the graphs \(G_1\) and \(G_2.\) Observe that though \(\mathscr P_3(G_1)=\mathscr P_3(G_2),\) the two graphs \(G_1\) and \(G_2\) are non-isomorphic.
(a) For \(r\geq 1,\) if \(\mathscr P_r(G)\) is complete, so is \(\mathscr P_{r+1}(G).\)
(b) For \(r=|V(G)|,\) \(\mathscr P_r(G)\) is the complete graph \(K_1.\)
So the natural question is, what is the minimum value of \(r,\) for which \(\mathscr P_r(G)\) is complete? The answer is given by the point completion number of a graph \(G\).
Definition 3.1. The point completion number \(pc(G)\) of a graph \(G\) is the least positive integer \(r\) for which \(\mathscr P_r(G)\) is a complete graph.
Observe that the point completion numbers of the grapsh \(G_1\) and \(G_2\) are 2 and 3, respectively.
Now we give some results related to the point completion number analogous to those of the line completion number given in [9].
Theorem 3.2. If \(H\) is an induced subgraph of a graph \(G\), then \(pc(H)\leq pc(G).\)
Proof. Let \(pc(H)=r\) and \(pc(G)=s.\) If \(s\) is more than the number of vertices in the subgraph \(H,\) then clearly, \(r\leq s.\) Assume that \(s\) is no more than the number of vertices in the subgraph \(H.\) We have to show that \(r\leq s.\) On contrary, suppose that \(r>s.\) Then all the \(s\)-subsets of \(V(G)\) are adjacent in the \(\mathscr P_s(G).\) But then all the \(s\)-subsets of \(V(H)\) are also adjacent, as \(H\) is induced subgraph of \(G.\) That means \(\mathscr P_s(H)\) is complete. Therefore, \(pc(H)\leq s,\) a contradiction. ◻
Note that if \(H\) is a subgraph of a graph \(G\) but not an induced one, then we may not get \(pc(H)\leq pc(G)\) (see Figure 3).
The following result gives lower and upper bounds for the point completion number. Note that these bounds are sharp.
Theorem 3.3. For any graph \(G\), \(\alpha\leq pc(G)\leq n,\) where \(n\) is the number of vertices and \(\alpha\) is the vertex independence number of \(G.\)
Proof. Clearly, \(pc(G)\leq n.\) We next show that \(pc(G)\geq\alpha.\) Let \(I=\{v_1, v_2, \dots, v_\alpha\}\subseteq V(G)\) be an independent set with the maximum cardinality in \(G.\) Let \(A\) and \(B\) be two subsets of \(V(G)\), each having cardinality \(\alpha -1,\) such that \(A=I\setminus v_\alpha\) and \(B=I\setminus v_1.\) Then the vertices \(A\) and \(B\) in \(\mathscr P _{\alpha -1}(G)\) are non-adjacent. So \(pc(G)>\alpha-1.\) In other words, \(pc(G)\geq\alpha.\) ◻
We can say that the independence number relates to \(lc(G)\) and \(pc(G)\) by constraining the structure of the corresponding super graphs.
We now explore the relationship between the line completion number and point completion number.
Theorem 3.4. \(lc(G)=pc(L(G)),\) where \(lc(G)\) is the line completion number of a graph \(G.\)
Proof. We observe that \(\mathscr L_1(G)=L(G)=\mathscr P_1(L(G)), \mathscr L_2(G)=\mathscr P_2(L(G)), \mathscr L_3(G)=\mathscr P_3(L(G)),\) …, \(\mathscr L_r(G)=\mathscr P_r(L(G)),\) and so on. Now \(\mathscr L_r(G)\) is complete if and only if \(\mathscr P_r(L(G))\) is complete. Hence, the result. ◻
From the above theorem, the study of super line graph and super point graph are identical if \(G\) is a line graph. But, if \(G\) is not a line graph, then the study of super line graph and super point graph are completely different.
We find the point completion numbers of some classes of graphs. The point completion number of several classes of graphs are known. The next theorem lists some of these. Note that, the line completion numbers of cycle on \(n\) vertices is same as that of path on \(n\) vertices [9]. But the point completion number turns out to be different for path and cycle on \(n\) vertices, when \(n\) is odd. The fan \(F_n\), the wheel \(W_n\), and the windmill \(M_n\) are the graphs \(K_1+P_n,~K_1+C_n\) and \(K_1+nK_2,\) respectively.
Theorem 3.5. (1) \(pc(P_n)=\left\lceil\frac{n}{2}\right\rceil.\)
(2) \(pc(C_n)=\left\lfloor\frac{n}{2}\right\rfloor.\)
(3) \(pc(K_{m,n})=n,\) if \(m\leq n.\)
(4) \(pc(Q_n)=2^{n-1}.\)
(5) \(pc(F_n)=\left\lceil\frac{n}{2}\right\rceil.\)
(6) \(pc(W_n)=\left\lfloor\frac{n}{2}\right\rfloor.\)
(7) \(pc(M_n)=n+1.\)
Proof. (1) Note that \(\mathscr P_r(P_n)\cong \mathscr L_r(P_{n+1}).\) Therefore, \(pc(P_n)=lc(P_{n+1})=\left\lfloor\frac{n+1}{2}\right\rfloor=\left\lceil\frac{n}{2}\right\rceil.\)
(2) Note that the line graph of a cycle is isomorphic to the cycle itself. Therefore, \(\mathscr P_r(C_n)\cong \mathscr L_r(C_n)\) and so \(pc(C_n)=lc(C_n)=\left\lfloor\frac{n}{2}\right\rfloor.\)
(3) Note that \(\alpha(K_{m,n})=n,\) if \(m \leq n.\) So \(pc(K_{m,n})\geq n.\) Our aim is to show that \(pc(K_{m,n})=n.\) Let \(X, Y\) be two arbitrary sets of vertices in \(K_{m,n}\) such that \(|X|=|Y|=n.\) Let \(M\cup N\) be the bipartition of \(V(K_{m,n}),\) such that \(|M|=m\) and \(|N|=n.\) If \(X\) intersects both \(M\) and \(N,\) then the vertices corresponding to \(X\) and \(Y\) are adjacent in \(\mathscr P_n(K_{m,n}).\) If \(X\) intersects only \(M,\) then \(m=n.\) But then either \(Y=N,\) or \(Y\) intersects both \(M\) and \(N.\) In either of the cases, the vertices corresponding to \(X\) and \(Y\) are adjacent in \(\mathscr P_n(K_{m,n}).\) Suppose \(X\) intersects only \(N.\) Then \(X=N.\) But again by a similar argument, the vertex corresponding to \(Y\) must be adjacent to the vertex corresponding to \(X\) in \(\mathscr P_n(K_{m,n}).\) As \(X\) and \(Y\) are arbitrary, \(\mathscr P_n(K_{m,n})\) is complete. Therefore, \(pc(K_{m,n})=n,\) for \(m\leq n.\)
(4) By Theorem 3.3, \(pc(Q_n)\geq 2^{n-1}.\) We prove that \(pc(Q_n)=2^{n-1}\). Let us assume, by contradiction, that \(pc(Q_n)>2^{n-1}\). Then there exist two different subsets \(X\) and \(Y\) of \(V(Q_n)\) each having \(2^{n-1}\) vertices such that \(X\) and \(Y\) are not adjacent in \(\mathscr P_{2^{n-1}}(Q_n).\) If \(X\cap Y = \phi,\) then \(Q_n\) is disconnected (as \(X\) and \(Y\) are non-adjacent in \(\mathscr P_{2^{n-1}}(Q_n)\)). This is a contradiction. Therefore, \(X\cap Y \neq \phi.\) Let \(x \in X \cap Y.\) Then \(x\) is not adjacent to any vertex in \(X\) or in \(Y.\) If \(\mid X\cap Y\mid = k,\) then \(1\leq k\leq 2^{n-1}.\) In \(Q_n,\) we observe that any independent set \(Z\) of \(m\) vertices has the property that neighbourhood \(N(Z)\) contain at least \(m\) vertices. Therefore, \(\mid N(X\cap Y)\mid \geq k.\) If \(\mid N(X\cap Y)\mid = k,\) then \(Q_n\) is disconnected which is a contradiction. Suppose that \(\mid N(X\cap Y)\mid > k.\) As \(X\) and \(Y\) are non-adjacent in \(\mathscr P_{2^{n-1}}(Q_n),\) there are at least \(k+1\) vertices which are not in \(X\cup Y.\) So \(\mid X\cup Y\mid +k+1=\mid X \mid +\mid Y \mid -\mid X\cap Y\mid +k+1=2^n+1\) which is a contradiction to number of vertices in \(Q_n.\) Therefore, \(X\) and \(Y\) must be adjacent in \(\mathscr P_{2^{n-1}}(Q_n).\) In fact, any two subsets of \(V(Q_n)\) each having \(2^{n-1}\) vertices are adjacent in \(\mathscr P_{2^{n-1}}(Q_n).\) So \(pc(Q_n)\leq 2^{n-1}.\)
The proofs of (5) and (6) follow on similar lines.
(7)
Let \(v_1, v_2, v_3, \cdots, v_{2n}, v\) be vertices of \(M_n\). If \(n\) is even, then we take \(X=\{v_1, v_2, v_3, \cdots, v_{n}\}\) and \(Y=\{v_{n+1}, v_{n+2}, v_{n+3}, \cdots, v_{2n}\}\). If \(n\) is odd, then we take \(X=\{v_1, v_2, v_3, \cdots, v_{n}\}\) and \(Y=\{v_{n}, v_{n+2}, v_{n+3}, \cdots, v_{2n}\}\). In both cases none of the vertices in \(X\) is adjacent to any vertex in \(Y.\) Therefore, \(X\) and \(Y\) are not adjacent in \(\mathscr P_n(M_n).\) So \(\mathscr P_n(M_n)\) is not complete. Therefore, \(pc(M_n)\geq n+1.\) On contrary assume \(pc(M_n)>n+1\). Then there exist two different subsets \(X\) and \(Y\) of \(V(M_n)\) each having \(n+1\) vertices such that \(X\) and \(Y\) are not adjacent in \(\mathscr P_{n+1}(M_n).\) If \(X\cap Y = \phi,\) then we get a contradiction to \(X, Y\) are non-adjacent in \(\mathscr P_{n+1}(M_n).\) Therefore, \(X\cap Y \neq \phi.\) Let \(x \in X \cap Y.\) Then \(x\) is not adjacent to any vertex in \(X\) or in \(Y.\) Clearly, \(x\neq v\). If \(\mid X\cap Y\mid = k,\) then \(1\leq k\leq n.\) As \(X\) and \(Y\) are non-adjacent in \(\mathscr P_{n+1}(M_n),\) there are at least \(k+1\) vertices which are not in \(X\cup Y.\) So \(\mid X\cup Y\mid +k+1=\mid X \mid +\mid Y \mid -\mid X\cap Y\mid +k+1=2n+3\) which is a contradiction to number of vertices in \(M_n.\) Therefore, \(X\) and \(Y\) must be adjacent in \(\mathscr P_{n+1}(M_n).\) In fact, any two subsets of \(V(M_n)\) each having \(n+1\) vertices are adjacent in \(\mathscr P_{n+1}(M_n).\) So \(pc(M_n)\leq n+1.\) Therefore, \(pc(M_n)=n+1.\) ◻
Bagga et al. [2] had proved that for \(n\geq 4\) and \(2\leq r \leq n-1\), \(\mathscr L_r(P_n)\) is pancyclic. Using this, we get a similar result as follows.
Theorem 3.6. For \(n\geq 3\) and \(2\leq r \leq n-1\), \(\mathscr P_r(P_n)\) is pancyclic.
Proof. The result follows immediately from \(\mathscr P_r(P_n)\cong \mathscr L_r(P_{n+1})\). ◻
Remark 3.7. \(\mathscr P_r(G)\) may not be pancyclic in general (check Figure [6]).
But for connected graphs, we pose the following conjecture.
Conjecture 3.8. Let \(G\) be a connected graph with \(n\) vertices. For \(n\geq 3\) and \(\left\lceil\frac{n}{2}\right\rceil \leq r \leq n-1\), \(\mathscr P_r(G)\) is pancyclic.
Theorem 3.9. Assume that G is a connected graph with \(n\) vertices. Then \(pc(G)=1\) if and only if \(G\) is \(K_n.\)
Proof. Proof follows from the definition of point completion number. ◻
Theorem 3.10. Let \(G\) be a graph with \(p\) vertices. Then \(pc(G)=p\) if and only if \(G\cong pK_1,\) null graph on \(p\) vertices.
Proof. If \(G\cong pK_1\), then clearly, \(pc(G)=p\). On the other hand, if \(pc(G)=p\), then there exists at least two sets (say) \(X\) and \(Y\) with \(p-1\) vertices each in \(G,\) such that \(X\) and \(Y\) are not adjacent in \(\mathscr P _{p-1}(G)\). Without loss of generality, let \(X=\{v_1,v_2,\cdots,v_{p-1}\}\) and \(Y=\{v_2,v_3,\cdots,v_{p}\}\). It follows that no two vertices of \(G\) are adjacent, and hence \(G\cong pK_1.\) ◻
As an immediate consequence, we get bounds for the point completion number of a connected graph.
Corollary 3.11. If \(G\) is a connected graph with \(p\) vertices, then \(\alpha \leq pc(G)\leq p-1.\)
Theorem 3.12.For graph \(G\), \(\chi (G)\leq \chi (\mathscr P_r(G)),\) where \(1\leq r \leq \mid V(G)\mid.\)
Proof. It is well known that if \(H\) is subgraph of \(G\), then the chromatic number \(\chi(H)\leq \chi(G)\). The rest is taken from Proposition 2.7, which says that every graph is a subgraph of its super point graph of index \(r\). ◻
Now we find the point completion numbers of \(P_n^k\) and \(C_n^k.\)
Theorem 4.1. \(pc(P_n^k)=\displaystyle \left\{\begin{array}{rcl}\displaystyle \left\lfloor\frac{n-k}{2}\right\rfloor+1 & \mbox{if} & k<n,\\ 1\hspace{.8cm} & \mbox{if} & k\geq n. \end{array}\right.\)
Proof. If \(k\geq n\) or \(n=k+1,\) then \(P^k_n\) is complete and hence we are done.
For \(k < n,\) we prove the result by contradiction. Let \(P_n~:~v_1-v_2-v_3-\cdots-v_n\) be path on \(n\) vertices. \(P_n^k\) is a graph with vertices \(v_1,~v_2,\ldots,v_n\) and two vertices are adjacent if their distance in \(P_n\) is less than or equal to \(k.\) Note that \(P_n\) is a subgraph of \(P_n^k\) and \(V(P_n)=V(P_n^k).\) Let \(X\) be the set of the first \(\left\lfloor\frac{n-k}{2}\right\rfloor\) vertices of \(P_n^k\) and \(Y\) be the set of the last \(\left\lfloor\frac{n-k}{2}\right\rfloor\) vertices in \(P_n^k.\) Note that none of the vertices in \(X\) is adjacent to any vertex in \(Y.\) Therefore no \(r\)-subsets of \(X\) is adjacent to any \(r\)-subset of \(Y,\) where \(1 \leq r \leq \left\lfloor\frac{n-k}{2}\right\rfloor.\) So \(\mathscr P_r(P_n^k)\) is not complete. Therefore, \(pc(P_n^k)\geq \left\lfloor\frac{n-k}{2}\right\rfloor+1.\) We prove that \(pc(P_n^k)=\left\lfloor\frac{n-k}{2}\right\rfloor+1= m\) (say). On contrary, suppose \(pc(P_n^k)>m.\) That means, there exist two \(m\)-subsets \(A\) and \(B\) of vertices in \(P_n\) such that \(A,~B\) are not adjacent in \(\mathscr P_m(P_n^k).\)
Case (1). \(A\cap B = \phi.\) Then \(|A|+|B|=2m=2\left\lfloor\frac{n-k}{2}\right\rfloor+2.\)
Now for \(k=1,\) we get a contradiction to \(A\cap B = \phi,\) and for \(k=2,\) we get a contradiction to \(A,~B\) are non-adjacent in \(\mathscr P_r(P_n^2).\)
Let \(k\geq 3.\) Now as \(A\) and \(B\) are non-adjacent in \(\mathscr P_r(P_n^k),\) there are at least \(k\) more vertices in \(P_n^k\) which are either adjacent to a vertex in \(A,\) or a vertex in \(B.\) But then we get a contradiction as \(|A|+|B|+k=2\left\lfloor\frac{n-k}{2}\right\rfloor+2+k>n=|V(P_n^k)|.\)
Case (2). \(A\cap B \neq \phi.\)
Now if a vertex \(v\in A\cap B\), then \(v\) is adjacent to any vertex neither in \(A\) nor in \(B,\) as \(A\) and \(B\) are assumed to be non-adjacent in \(\mathscr P_m(P_n^k).\) In fact, vertices in \(A\cap B\) form an independent set of \(P_n^k.\) Therefore, if \(|A\cap B|=x,\) then \(1\leq x\leq \left\lceil\frac{n}{k+1}\right\rceil.\) Moreover, the distance between any two vertices in \(A\cap B\) would be greater than \(k,\) being elements of an independent set in \(P_n^k.\) As \(A,~B\) are non-adjacent in \(\mathscr P_m(P_n^k),\) there are at least \(x(k+1)\) vertices which are not in \(A\cup B.\) (Check the following example for more clarity.) But then \(|A\cup B|+x(k+1)=|A|+|B|-|A\cap B|+x(k+1)=n-k+2-x+x(k+1)=n+2+(x-1)>n,\) again a contradiction. Therefore, there do not exist any two \(m\)-vertices which are not adjacent in \(\mathscr P_m(P_n^k).\) ◻
Example 4.2. Consider \(A=\{v_1,v_2,v_5,v_8\}\) and \(B=\{v_5,v_8,v_{11},v_{12}\}\). Then \(A\) and \(B\) are not adjacent in \(\mathscr P_4(P_{12}^2).\) Now \(v_5\) and \(v_8\) are not adjacent to any vertex in \((A\cup B)-\{v_5,v_8\}=\{v_1,v_2,v_{11},v_{12}\}\) and \(\{v_5,v_8\}\) form an independent vertex set of \(P^2_{12}\). So \(\{v_3,v_4,v_6,v_7,v_9,v_{10}\}\cap (A\cup B)= \phi.\)
We use a similar technique to find the point completion number of \(C_n^k.\)
Theorem 4.3. \(pc(C_n^k)=\displaystyle \left\{\begin{array}{rcl}\displaystyle \left\lfloor\frac{n-2k}{2}\right\rfloor+1 & \mbox{if} & 1+2k<n, \\ 1\hspace{.8cm} & \mbox{if} & 1+2k\geq n. \end{array}\right.\)
Proof. If \(1+2k\geq n,\) then \(C^k_n\) is complete and hence we are done.
For \(1+2k < n,\) we prove the result by contradiction. Let \(C_n~:~x_1-x_2-x_3-\cdots-x_n-x_1\) be a cycle on \(n\) vertices. Then \(C_n^k\) is the graph with the same vertex set as \(C_n,\) with two vertices being adjacent if their distance in \(C_n\) is less than or equal to \(k.\) Obviously, \(C_n\) is a subgraph of \(C_n^k.\) Let \(X=\left\lbrace x_1, x_2, \dots , x_{\left\lfloor\frac{n-2k}{2}\right\rfloor}\right\rbrace\) and \(Y=\left\lbrace x_{\left\lfloor\frac{n-2k}{2}\right\rfloor+k+1}, x_{\left\lfloor\frac{n-2k}{2}\right\rfloor+k+2}, \dots , x_{ 2\left\lfloor\frac{n-2k}{2}\right\rfloor+k} \right\rbrace.\) Then \(X\) and \(Y\) are non-adjacent in \(\mathscr P_r(C_n^k).\) Therefore, \(pc(C_n^k)\geq \left\lfloor\frac{n-2k}{2}\right\rfloor+1.\)
We prove that \(pc(C_n^k)=\left\lfloor\frac{n-2k}{2}\right\rfloor+1= m\) (say). Suppose if possible that \(pc(C_n^k)>m.\) Then there must exist two different \(m-\)subsets \(A\) and \(B\) of vertices in \(C_n\), such that \(A\) and \(B\) are not adjacent in \(\mathscr P_{m} (C_n^k)\). We have the following two possibilities.
Case(1). \(A\cap B = \phi.\) If \(A\) and \(B\) in \(\mathscr P_m(C_n^k)\) are not adjacent, then at least \(2k\) vertices are adjacent to vertices in \(A\) and \(B.\) But then \(\mid A\mid +\mid B\mid +2k= \left\lfloor\frac{n-2k}{2}\right\rfloor+1+\left\lfloor\frac{n-2k}{2}\right\rfloor+1+2k=2\left( \left\lfloor\frac{n-2k}{2}\right\rfloor+k+1\right)>n\), a contradiction to the number of vertices in \(C_n^k.\)
Case(2). Let \(A\cap B\neq \phi.\) But \(A\) and \(B\) are non-adjacent in \(\mathscr P_m(C_n^k)\). So \(A\cap B\) must be an independent set. Moreover, we must have \(1\leq |A\cap B| \leq \left\lfloor\frac{n}{k+1}\right\rfloor\).
Suppose \(|A\cap B|=x.\) Note that \(C_n^k\) is a \(2k\)-regular graph. Moreover, being vertices of an independent set in \(C_n^k\), the distance between any two vertices of \(A\cap B\) is greater than \(k.\) Therefore there are at least \(kx+2k\) vertices which are not in \(A\cup B.\) (Verify with the example given below.) But this leads to a contradiction as \(|A\cup B|+kx+2k=\left\lfloor\frac{n-2k}{2}\right\rfloor+1+\left\lfloor\frac{n-2k}{2}\right\rfloor+1-x+kx+2k>n,\) the number of vertices in \(C_n^k.\) Therefore \(A\) and \(B\) must be adjacent in \(\mathscr P_m(C_n^k).\) ◻
Example 4.4. Let \(A=\{x_1,x_4,x_7\}\) and \(B=\{x_4,x_7,x_{10}\}\). Then \(A\) and \(B\) are not adjacent in \(\mathscr P_3(C_{12}^2).\) Now, \(x_4\) and \(x_7\) form an independent set in \(C^2_{12}\). So \(\{x_2,x_3,x_5,x_6,x_8,x_9,x_{11},x_{12}\}\cap (A\cup B)= \phi.\)
The line completion number and point completion number serve as vital topological indices, offering insights into graph connectivity and structure. By extending the study to super point graphs, we open avenues for exploring vertex-centric properties in tandem with edge-based measures. Future work will focus on algorithmic approaches to compute these indices efficiently and explore their applications in various fields.