![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
The status of a vertex , denoted by
, is the sum of the distances between
and all other vertices in a graph
. The first and second status connectivity indices of a graph
are defined as
and
respectively, where
denotes the edge set of
. In this paper we have defined the first and second status co-indices of a graph
as
and
respectively. Relations between status connectivity indices and status co-indices are established. Also these indices are computed for intersection graph, hypercube, Kneser graph and achiral polyhex nanotorus.
1 Introduction
The graph theoretic models can be used to study the properties of molecules in theoretical chemistry. The oldest well known graph parameter is the Wiener index which was used to study the chemical properties of paraffins [Citation1]. The Zagreb indices were used to study the structural property models [Citation2,3]. Ramane and Yalnaik [Citation4] obtained the status connectivity indices and analyzed its correlation with the boiling point of benzenoid hydrocarbons. In this paper we define the status co-indices of a graph and establish the relations between the status connectivity indices and status co-indices. Also we obtain the bounds for the status connectivity indices of connected complement graphs. Further we compute these status indices for intersection graph, hypercube, Kneser graph and achiral polyhex nanotorus.
Let be a connected graph with
vertices and
edges. Let
be the vertex set of
and
be an edge set of
. The edge joining the vertices
and
is denoted by
. The degree of a vertex
in a graph
is the number of edges incident to
and is denoted by
. The distance between the vertices
and
is the length of shortest path joining
and
and is denoted by
. The diameter of
is the maximum distance between all pair of vertices of
and is denoted by
.
The status (or transmission) of a vertex , denoted by
is defined as [Citation5],
A connected graph is self-median if the value
is constant for all vertices
of
[Citation6]. A graph
is distance-balanced if for all edges
of
, the following equality holds [Citation7,8],
Balakrishnan et al. [Citation9] noticed that the concepts of distance-balanced and self-median are the same. A connected graph is distance-balanced if and only if it is self-median.
A connected graph is said to be
-distance-balanced if
for every vertex
.
The Wiener index of a connected graph
is defined as [Citation1],
More results about Wiener index can be found in [10–16].
The first and second Zagreb indices of a graph are defined as [Citation2]
Results on the Zagreb indices can be found in [17–23].
The first and second Zagreb co-indices of a graph are defined as [Citation24]
More results on Zagreb co-indices can be found in [25,26].
The first status connectivity index and second status connectivity index
of a graph
are defined as [Citation4]
(1)
(1)
We observe that the first status connectivity index is nothing but the degree distance of a graph introduced by Dobrynin and Kotchetova [Citation27] and Gutman [Citation28]. The degree distance of is
The degree distance of graphs is well studied in the literature [29–36].
Analog to Eq. (1) and the definition of Zagreb co-indices, we define the first status co-index and the second status co-index
as
For a graph given in , ,
,
and
.
2 Status connectivity indices and co-indices
In [Citation4] the results on status connectivity indices are obtained. In this section we obtain further results on the status connectivity indices and co-indices of graphs.
Proposition 2.1
Let be a connected graph on
vertices. Then
and
Proof
Also
Corollary 2.2
Let be a connected graph with
vertices,
edges and
. Then
and
Proof
For any graph of
,
and
Also
and
[Citation4]. Therefore by Proposition 2.1,
and
Proposition 2.3
Let be a connected graph with
vertices,
edges and
. Then
and
Proof
For any graph of
,
. Therefore
and
Proposition 2.4
Let be a graph with
vertices and
edges. Let
be the complement of
and it is connected. Then
and
Equality in both cases holds if and only if
.
Proof
For any vertex in
there are
vertices which are at distance
and the remaining
vertices are at distance at least
. Therefore
Therefore,
And
For equality: If the diameter of is
or
then the equality holds.
Conversely, let .
Suppose, , then there exists at least one pair of vertices, say
and
such that
.
Therefore . Similarly
and for all other vertices
of
,
.
Partition the edge set of into three sets
,
and
, where
and
It is easy to check that
,
and
.
Therefore
which is a contradiction. Hence
.
The equality of can be proved analogously.
3 Status connectivity indices and co-indices of some distance-balanced graphs
A bijection on
is called an automorphism of
if it preserves
. In other words,
is an automorphism if for each
,
if and only if
. Let
It is known that
forms a group under the composition of mappings. A graph
is called vertex-transitive if for every two vertices
and
of
, there exists an automorphism
of
such that
. It is known that any vertex-transitive graph is vertex degree regular, distance-balanced and self-centered. The graph depicted in is 14-distance-balanced graph but not degree regular and therefore not vertex-transitive (see [37,38]).
The following lemma is straightforward from the definition of status connectivity indices.
Lemma 3.1
Let be a connected
-distance-balanced graph with
edges. Then
and
Theorem 3.2
[Citation39] Let be a connected graph on
vertices with the automorphism group
and the vertex set
. Let
be all orbits of the action
on
. Suppose that for each
,
are the status of vertices in the orbit
. Then
Specially, if
is vertex-transitive (that is,
), then
, where
is the status of each vertex of
.
Analogous to Theorem 3.2 and as a consequence of Proposition 2.1, we have the following.
Theorem 3.3
Let be a connected graph on
vertices with the automorphism group
and the vertex set
. Let
be all orbits of the action
on
. Suppose that for each
,
and
are the vertex degree and the status of vertices in the orbit
, respectively. Then
Specially, if
is vertex-transitive (that is,
), then
where
and
are the degree and the status of each vertex of
respectively.
The following is a direct consequence of Proposition 2.1, Lemma 3.1 and Theorem 3.2.
Lemma 3.4
Let be a connected
-distance-balanced graph with
edges. Then
Let be a set and
be a non-empty family of distinct non-empty subsets of
such that
. The intersection graph [Citation40] of
which is denoted by
has
as its set of vertices and two distinct vertices
and
,
, are adjacent if and only if
. Here we will consider a set
of cardinality
and let
be the set of all subsets of
of cardinality
,
, which is denoted by
. Upon convenience we may set
. Let us denote the intersection graph
by
. The number of vertices of this graph is
and the degree
of each vertex is as follows:
The number of its edges is as follows:
Lemma 3.5
[Citation41] The intersection graph is vertex-transitive and for any
-element subset
of
we have
Moreover,
Theorem 3.6
For intersection graph ,
Proof
It is a direct consequence of Theorem 3.3 and Lemma 3.5.
The vertex set of the hypercube consists of all
-tuples
with
. Two vertices are adjacent if the corresponding tuples differ in precisely one place. Moreover,
has exactly
vertices and
edges. Darafsheh [Citation41] proved that
is vertex-transitive and for every vertex
,
. Therefore, by Lemmas 3.1 and 3.4 we have following result.
Theorem 3.7
For hypercube ,
The Kneser graph is the graph whose vertices correspond to the
-element subsets of a set of
elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Clearly we must impose the restriction
. The Kneser graph
has
vertices and it is regular of degree
. Therefore the number of edges of
is
(see [Citation42]). The Kneser graph
is the complete graph on
vertices. The Kneser graph
is known as the odd graph
. The odd graph
is isomorphic to the Petersen graph (see ).
Lemma 3.8
[Citation42] The Kneser graph is vertex-transitive and for each
-subset
,
.
Following proposition follows from Lemmas 3.8 and 3.1.
Proposition 3.9
For a Kneser graph we have
and
Following proposition follows from Proposition 2.1, Lemma 3.8 and Proposition 3.9.
Proposition 3.10
For a Kneser graph we have
and
A nanostructure called achiral polyhex nanotorus (or toroidal fullerenes) of perimeter and length
, denoted by
is depicted in and its 2-dimensional molecular graph is in . It is regular of degree 3 and has
vertices and
edges.
The following lemma was proved in [39,43].
Lemma 3.11
[39,43] The achiral polyhex nanotorus is vertex-transitive such that for an arbitrary vertex
,
The following is a direct consequence of Lemmas 3.1 and 3.11.
Corollary 3.12
Let be a achiral polyhex nanotorus. Then
and
Corollary 3.13
Let be a achiral polyhex nanotorus. Then
and
Proof
Since and polyhex nanotorus
has
vertices, by Lemma 3.11, the Wiener index of polyhex nanotorus
is as follows Citation43]:
Substituting this and Corollary 3.12 in Proposition 2.1 we get the results.
Acknowledgments
Authors are thankful to the referees for their suggestions. The first author HSR is thankful to the University Grants Commission (UGC), New Delhi, India for support through grant under UGC-SAP DRS-III, 2016–2021: F.510/3/DRS-III /2016 (SAP-I). The second author ASY is thankful to the University Grants Commission (UGC), New Delhi, India for support through Rajiv Gandhi National Fellowship No. F1-17.1/2014–15/RGNF-2014-15-SC-KAR-74909.
References
- WienerH., Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69 1947 17–20
- GutmanI., TrinajstićN., Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17 1972 535–538
- TodeschiniR., ConsonniV., Handbook of Molecular Descriptors 2000Wiley-VCH Weinheim
- RamaneH.S., YalnaikA.S., Status connectivity indices of graphs and its applications to the boiling point of benzenoid hydrocarbons, J. Appl. Math. Comput., 55 2017 609–627
- HararyF., Status and contrastatus, Sociometry, 22 1959 23–43
- CabelloS., LukšičP., The complexity of obtaining a distance-balanced graph, Electron. J. Combin., 18 2011 Paper 49
- HandaK., Bipartite graphs with balanced (a,b)-partitions, Ars Combin., 51 1999 113–119
- JerebicJ., KlavžarS., RallD.F., Distance-balanced graphs, Ann. Comb., 12 2008 71–79
- BalakrishnanK., ChangatM., PeterinI., ŠpacapanS., ŠparlP., SubhamathiA.R., Strongly distance-balanced graphs and graph products, European J. Combin., 30 2009 1048–1053
- DasK.C., GutmanI., Estimating the Wiener index by means of number of vertices, number of edges and diameter, MATCH Commun. Math. Comput. Chem., 64 2010 647–660
- DobryninA.A., EntringerR., GutmanI., Wiener index of trees: theory and applications, Acta Appl. Math., 66 2001 211–249
- GutmanI., YehY., LeeS., LuoY., Some recent results in the theory of the Wiener number, Indian J. Chem., 32A 1993 651–661
- NikolićS., TrinajstićN., MihalićZ., The Wiener index: development and applications, Croat. Chem. Acta, 68 1995 105–129
- RamaneH.S., ManjalapurV.V., Note on the bounds on Wiener number of a graph, MATCH Commun. Math. Comput. Chem., 76 2016 19–22
- RamaneH.S., RevankarD.S., GanagiA.B., On the Wiener index of a graph, J. Indones. Math. Soc., 18 2012 57–66
- WalikarH.B., ShigehalliV.S., RamaneH.S., Bounds on the Wiener number of a graph, MATCH Commun. Math. Comput. Chem., 50 2004 117–132
- BorovicaninB., DasK.C., FurtulaB., GutmanI., Zagreb indices: bounds and extremal graphs GutmanI., FurtulaB., DasK.C., MilovanovicE., MilovanovicI.Bounds in Chemical Graph Theory - Basics2017Uni. Kragujevac Kragujevac 67–153
- DasK.C., XuK., NamJ., Zagreb indices of graphs, Front. Math. China, 10 2015 567–582
- GutmanI., DasK.C., The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem., 50 2004 83–92
- GutmanI., FurtulaB., Kovijanić VukićevićŽ., PopivodaG., On Zagreb indices and coindices, Math. Comput. Chem., 74 2015 5–16
- KhalifehM.H., Yousefi-AzariH., AshrafiA.R., The first and second Zagreb indices of some graph operations, Discrete Appl. Math., 157 2009 804–811
- NikolićS., KovačevićG., MiličevićA., TrinajstićN., The Zagreb indices 30 years after, Croat. Chem. Acta, 76 2003 113–124
- ZhouB., GutmanI., Further properties of Zagreb indices, MATCH Commun. Math. Comput. Chem., 54 2005 233–239
- DošlićT., Vertex-weighted Wiener polynomials for composite graphs, Ars Math. Contemp., 1 2008 66–80
- AshrafiA.R., DošlićT., HamzehA., The Zagreb coindices of graph operations, Discrete Appl. Math., 158 2010 1571–1578
- AshrafiA.R., DošlićT., HamzehA., Extremal graphs with respect to the Zagreb coindices, MATCH Commun. Math. Comput. Chem., 65 2011 85–92
- DobryninA.A., KochetovaA.A., Degree distance of a graph: a degree analogue of the Wiener index, J. Chem. Inf. Comput. Sci., 34 1994 1082–1086
- GutmanI., Selected properties of the Schultz molecular topological index, J. Chem. Inf. Comput. Sci., 34 1994 1087–1089
- BucicovschiO., CioabăS.M., The minimum degree distance of graphs of given order and size, Discrete Appl. Math., 156 2008 3518–3521
- DankelmannP., GutmanI., MurkembiS., SwartH.C., On the degree distance of a graph, Discrete Appl. Math., 157 2009 2773–2777
- DasK.C., SuG., XiongL., Relation between degree distance and Gutman index of graphs, MATCH Commun. Math. Comput. Chem., 76 2016 221–232
- IlićA., StevanovićD., FengL., YuG., DankelmannP., Degree distance of unicyclic and bicyclic graphs, Discrete Appl. Math., 159 2011 779–788
- TomescuA.I., Unicyclic and bicyclic graphs having minimum degree distance, Discrete Appl. Math., 156 2008 125–130
- TomescuI., Some extremal properties of the degree distance of a graph, Discrete Appl. Math., 98 1999 159–163
- TomescuI., Properties of connected graphs having minimum degree distance, Discrete Math., 309 2009 2745–2748
- WangH., KangL., Further properties on the degree distance of graphs, J. Comb. Optim., 31 2016 427–446
- AouchicheM., CaporossiG., HansenP., Variable neighborhood search for extremal graphs, 8. Variations on Graffiti 105, Congr. Numer., 148 2001 129–144
- AouchicheM., HansenP., On a conjecture about the Szeged index, European J. Combin., 31 2010 1662–1666
- AshrafiA.R., Wiener index of nanotubes, toroidal fullerenes and nanostars CataldoF., GraovacA., OriO.The Mathematics and Topology of Fullerenes2011Springer Netherlands Dordrecht 21–38
- HararyF., Graph Theory 1968Addison Wesley Reading
- DarafshehM.R., Computation of topological indices of some graphs, Acta Appl. Math., 110 2010 1225–1235
- MohammadyariR., DarafshehM.R., Topological indices of the Kneser graph KGn,k, Filomat, 26 2012 665–672
- YousefiS., Yousefi-AzariH., AshrafiA.R., KhalifehM.H., Computing Wiener and Szeged indices of an achiral polyhex nanotorus, J. Sci. Univ. Teharan, 33 2008 7–11