![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
In 1992, Bagga, Beineke, and Varma introduced the concept of the super line graph of index of a graph
denoted by
The vertices of
are the
-subsets of
and two vertices
and
are adjacent if there exist
and
such that
and
are adjacent edges in
They also defined the line completion number
of graph G to be the minimum index
for which
is complete. They found the line completion number for certain classes of graphs. In this paper, we find the line completion number of hypercube
for every
.
1 Introduction
The line graph of a graph
is defined to have as its vertices the edges of
with two being adjacent if the corresponding edges share a vertex in
Many properties of the line graphs follow by translating the properties of the underlying graph from vertices into edges. Line graphs have been studied for over seventy five years. A motivation behind studying the line graphs had been a search for simpler algorithms for solving some hard problems.
Table
Over the period, various generalizations of the line graphs have been invented and studied, including the line graphs of line graphs, line graphs of multigraphs, line graphs of hypergraphs, and line graphs of weighted graphs, etc. Prisner [Citation1] describes many interesting generalizations of the line graphs. Bagga [Citation2] has written a survey article on the generalizations of line graphs. In most generalizations of the line graphs, the vertices of the new graph are taken to be another family of subgraphs of and adjacency is defined in terms of an appropriate intersection.
Bagga et al. [Citation3] introduced the concept of the super line graph of a graph
as follows.
Definition 1.1
For a given graph its super line graph
of index
is the graph whose vertices are the
-subsets of
and two vertices
and
are adjacent if there exist
and
such that
and
are adjacent edges in
From the definition, it turns out that coincides with the line graph
Bagga et al. [3–8Citation[3]Citation[4]Citation[5]Citation[6]Citation[7]Citation[8]] have done extensive work on the super line graphs. They discussed various properties of super line graphs in [Citation3,Citation4]. In [Citation5], they found several results on the independence number of super line graphs of arbitrary index and on pancyclicity in the index-2 case. They discussed the structure and properties of super line graphs of index at a length in [Citation6]. K.J.Bagga and Vasquez in [Citation9] have studied super line graphs of index
for hypercubes.
One of the important properties of super line graphs is that, if is complete, so is
Motivated by this, Bagga et al. [Citation8] defined the line completion number of a graph. They determined the line completion numbers for various classes of graphs, viz., complete graph, path, cycle, fan, windmill, wheel, etc. Recently, they determined line completion number of complete bipartite graphs in [Citation7]. Certain graphs are also characterized with the help of line completion number.
Definition 1.2
The line completion number of a graph
is the least positive integer
for which
is a complete graph.
Note that the lower bound for is
more than the minimum number of vertices in either of the sets that form a partition of vertex set of
into two sets. For some graphs, the maximum of these numbers is the line completion number. For example, this is the case for complete graphs, and, as we shall see, for hypercubes. In this paper, we determine the line completion number of hypercube
for every
A hypercube is the graph whose vertex set is the set of
binary
-tuples, and edge set consists of those pairs of vertices which differ in exactly one co-ordinate. Therefore
is an
-regular graph with
vertices and
edges. Also, for any
is the cartesian product of
and
i.e.,
shows some elementary hypercubes.
We prove the following theorem.
Theorem
For any
Interestingly, this number is more than the number of edges in the half cube
For the proof, we need a result related to the maximum number of edges in an induced subgraph of
on
vertices. Hart [Citation10] has given the required formula, which looks simple, but is tedious to workout. We state the same result in other words and prove that both the formulae are same. We do this preliminary work out in Section 2 and proof of the theorem is given in Section 3.
2 Preliminaries
Hart [Citation10] found a set of vertices of a given size in the hypercube which has the maximum number of interconnecting edges. He denoted for any non-negative integer
as the sum of its binary digits, i.e., the number of ones there. Then one has the following obvious lemma.
Lemma 2.1
[Citation10]
For all
He proved the following proposition.
Proposition 2.2
For any and
satisfying
the maximum number of edges
in the induced subgraph on
vertices is given by
Though the above formula for finding the maximum number of edges on the induced subgraph of having
vertices looks simple, one needs to know the binary representations of all the digits from
to
In 2013, Li and Yang [Citation11] found
in terms of the binary representation of
only. We prove the same result in a much simpler way and prove that the formula which we obtain is same as the above.
Lemma 2.3
For any with
Proof
For calculating one needs to know the number of
’s appearing in the binary representations of all the numbers from
to
See the table given below.
We have divided the table into blocks corresponding to the binary representations of the digits from to
to
,
to
,…,
to
By Lemma 2.1, the total number of
’s in these blocks is equal to
In addition to them, number of ’s in
column is equal to
number of
’s in
column is equal to
and so on.
Therefore the total number of ’s in the binary representations of
to
is
But on simplifying the above summations, we get the desired formula. □
3 Proof of the main theorem
Theorem 3.1
For any
Proof
Recall that the vertex set of consists of the binary
-tuples and two vertices are adjacent, if their corresponding tuples differ in exactly one component. Let
be the set of edges in
whose both end vertices start with
While
be the set of edges in
whose both end vertices start with
For
the vertices corresponding to
and
in
are non-adjacent. So we call
and
to be “disjoint” subsets. Therefore,
We prove that
Suppose not. Then there exist two subsets and
of
each having
elements such that they are disjoint. We have the following two cases.
(I). Suppose is odd.
We partition the into the following
spanning subgraphs.
Let be the set of rectangles created by varying the first two components of the binary
-tuples of
be the set of rectangles created by varying third and fourth components,
be the set of rectangles created by varying fifth and sixth components,…,
be the set of rectangles created by varying
and
components.
be the set of edges formed by varying the
th component of the binary
-tuples of
It can be easily observed that ’s are all
-regular, spanning subgraphs of
while
is a perfect matching.
Let
Then
For we have
Therefore, by Pigeonhole Principle, and
or
and
Case 1. and
Part (a). Assume that
Now we try to prove the result for equality, as it is the minimal case. Suppose If the edges in
(similarly
) form rectangles, they need number of vertices equal to
which is minimum. Similarly, if the edges form matching, they need
vertices, which is maximum. Therefore,
Now we take different subcases according to the number of vertices required for
and
Subcase (i). Suppose By Lemma 2.3, induced subgraph of
on
vertices can have at the most
edges. Therefore
can have at the most
edges on
Similarly,
can have at the most
edges on
Now we are left with
vertices. Again by Lemma 2.3, one can have at the most
edges in the induced subgraph on these vertices. But we need
more edges for the sets
and
which is not possible.
Subcase (ii). Suppose and
By Lemma 2.3,
can have at the most
edges on
While
can have at the most
edges on
We are left with
vertices. Again by Lemma 2.3, one can have at the most
edges in the induced subgraph on these vertices. But we need
more edges for the sets
and
which is not possible.
Subcase (iii). Suppose be the maximum possible, when
Then
By Lemma 2.3,
can have at the most
edges on
and from above,
can have at the most
edges on
Note that all the vertices of
are exhausted by
and
But we still need
more edges, which is not possible.
Subcase (iv). Note that this case is not possible, as it exceeds
the total number of vertices in
It should be noted that, proving the result for the minimal cases is sufficient here. For, if we choose and
then obviously the number of vertices on which the edges are incident are more. This leads to an insufficient number of edges required for forming sets
and
which are disjoint.
Part (b). Suppose This is possible only for
So we have
In this case also it suffices to assume only one common edge, as due to large number of common edges number of vertices available for the choice of remaining edges get reduced and one can easily get a contradiction. Also, we work out the subcase which is analogues to the Subcase (i) of the Part (I) only, as the remaining cases can be worked out in a similar manner.
Suppose Then
and hence,
But again by the similar arguments as in the above case, we get a contradiction.
Case 2. and
Again, we work out the minimal case only, i.e., the case of equality of both the quantities stated above.
Suppose
Then and
By Lemma 2.3, one can have at the most
edges on an induced subgraph with
vertices, while
edges on the induced subgraph with
vertices. Therefore,
can have at the most
edges on
and
can have at the most
edges on
Now we are left with
vertices and the induced subgraph on these vertices can have at the most
edges, by Lemma 2.3. But we need
more edges, which is not possible.
Therefore by Cases 1 and 2, it is clear that for odd
(II). Suppose is even.
We partition the into the spanning subgraphs
where
is the set of rectangles created by varying
and
components,
So
The rest of the proof for this case follows on the similar lines as in (I).
Therefore, for every
□
4 Concluding remark
Line completion numbers of hypercube variants can also be computed in a similar manner as above. So we have the following table.
Notes
Peer review under responsibility of Kalasalingam University.
References
- Prisner E. Graph Dynamics Pitman Research Notes in Mathematics Series vol. 338 (1995) Long-man. Harlow.
- Bagga J.S. Old and new generalizations of line graphs IJMMS 29 2004 1509 1521
- Bagga K.S. Beineke L.W. Varma B.N. Super line graphs Graph Theory Combin. Algorithms 1–2 1992 35 46
- Bagga J.S. Beineke L.W. Varma B.N. Super line graphs and their properties Combin. Graph Theory Algorithms Appl. 1994 1 6
- Bagga J.S. Beineke L.W. Varma B.N. Independence and cycles in super line graphs Australas. J. Combin. 19 1999 171 178
- Bagga J.S. Beineke L.W. Varma B.N. The super line graph ℒ2(G) Discrete Math. 206 1–3 1999 51 61
- Bagga J.S. Beineke L.W. Varma B.N. A number theoretic problem on super line graphs AKCE Int. J. Graphs Combin. 13 2016 177 190
- Bagga K.S. Beineke L.W. Varma B.N. The line completion number of a graph Graph Theory Combin. Algorithms 1–2 1995 1197 1201
- Bagga K.J. Vasquez M.R. The super line graph ℒ2 for hypercubes Congr. Numer. 93 1993 111 113
- Hart S. A note on the edges of the n-cube Discrete Math. 14 1976 157 163
- Li H. Yang W. Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes Discrete Appl. Math. 161 2013 2753 2757