Given a finite graph
G
, the maximum length of a sequence
(
v
1
,
…
,
v
k
)
of vertices in
G
such that each
v
i
dominates a vertex that is not dominated by any vertex in
{
v
1
,
…
,
v
i
-
1
}
is ...called the Grundy domination number,
γ
gr
(
G
)
, of
G
. A small modification of the definition yields the Z-Grundy domination number, which is the dual invariant of the well-known zero forcing number. In this paper, we prove that
γ
gr
(
G
)
≥
n
+
⌈
k
2
⌉
-
2
k
-
1
holds for every connected
k
-regular graph of order
n
different from
K
k
+
1
and
2
C
4
¯
. The bound in the case
k
=
3
reduces to
γ
gr
(
G
)
≥
n
2
, and we characterize the connected cubic graphs with
γ
gr
(
G
)
=
n
2
. If
G
is different from
K
4
and
K
3
,
3
, then
n
2
is also an upper bound for the zero forcing number of a connected cubic graph, and we characterize the connected cubic graphs attaining this bound.
We obtain new results on the 2-rainbow domination number of generalized Petersen graphs P(ck,k). Exact values are established for all infinite families where the general lower bound 45ck is attained. ...In all other cases lower and upper bounds with small gaps are given.
Szeged, PI and Mostar indices are some of the most investigated distance‐based molecular descriptors. Recently, many different variations of these topological indices appeared in the literature and ...sometimes they are all together called Szeged‐like topological indices. In this paper, we formally introduce the concept of a general Szeged‐like topological index, which includes all mentioned indices and also infinitely many other topological indices that can be defined in a similar way. As the main result of the paper, we provide a cut method for computing a general Szeged‐like topological index for any strength‐weighted graph. This greatly generalizes various methods known for some of the mentioned indices and therefore rounds off such investigations. Moreover, we provide applications of our main result to benzenoid systems, phenylenes, and coronoid systems, which are well‐known families of molecular graphs. In particular, closed‐form formulas for some subfamilies of these graphs are deduced.
Szeged‐like topological indices, such as Szeged, PI, and Mostar indices, are some of the most investigated distance‐based molecular descriptors. We provide a cut method for computing a general Szeged‐like topological index for any strength‐weighted graph, which greatly generalizes various previous results. It reduces the problem of calculating a topological index to the problem of calculating the corresponding indices of quotient graphs. Moreover, applications of our main result to some molecular graphs are presented.
There exist many topological indices that are calculated on saturated hydrocarbons since they can be easily modelled by simple graphs. On the other hand, it is more challenging to investigate ...topological indices for hydrocarbons with multiple bonds. The purpose of this paper is to introduce a simple model that gives good results for predicting physico-chemical properties of alkenes and alkadienes. In particular, we are interested in predicting boiling points of these molecules by using the well known Wiener index and its weighted versions. By performing the non-linear regression analysis we predict boiling points of alkenes and alkadienes.
Szeged, Padmakar-Ivan (PI), and Mostar indices are some of the most investigated distance-based Szeged-like topological indices. On the other hand, the polynomials related to these topological ...indices were also introduced, for example the Szeged polynomial, the edgeSzeged polynomial, the PI polynomial, the Mostar polynomial, etc. In this paper, we introduce a concept of the general Szeged-like polynomial for a connected strength-weighted graph. It turns out that this concept includes all the above mentioned polynomials and also infinitely many other graph polynomials. As the main result of the paper, we prove a cut method which enables us to efficiently calculate a Szeged-like polynomial by using the corresponding polynomials of strength-weighted quotient graphs obtained by a partition of the edge set that is coarser than Θ∗ -partition. To the best of our knowledge, this represents the first implementation of the famous cut method to graph polynomials. Finally, we show how the deduced cut method can be applied to calculate some Szeged-like polynomials and corresponding topological indices of para-polyphenyl chains and carbon nanocones.
Szeged and Mostar root-indices of graphs Brezovnik, Simon; Dehmer, Matthias; Tratnik, Niko ...
Applied mathematics and computation,
04/2023, Letnik:
442
Journal Article
Recenzirano
Odprti dostop
•We introduce several Szeged and Mostar root-indices of graphs.•The root-indices are defined as unique positive roots of modified graph polynomials.•Various analytical results of root-indices are ...derived.•Discrimination, correlations, structure sensitivity, and abruptness are calculated.•The obtained numerical results are compared with the already known similar descriptors.
Various distance-based root-indices of graphs are introduced and studied in the present article. They are obtained as unique positive roots of modified graph polynomials. In particular, we consider the Szeged polynomial, the weighted-product Szeged polynomial, the weighted-plus Szeged polynomial, and the Mostar polynomial. We derive closed formulas of these polynomials for some basic families of graphs. Consequently, we provide closed formulas for some root-indices and examine the convergence of sequences of certain root-indices. Moreover, some general properties of studied root-indices are stated. Finally, numerical results related to discrimination power, correlations, structure sensitivity, and abruptness of root-indices are calculated, interpreted, and compared to already known similar descriptors.
A catacondensed even ring system (shortly CERS) is a simple bipartite 2-connected outerplanar graph with all vertices of degree 2 or 3. In this paper, we investigate the resonance graphs (also called ...Z-transformation graphs) of CERS and firstly show that two even ring chains are evenly homeomorphic iff their resonance graphs are isomorphic. As the main result, we characterize CERS whose resonance graphs are daisy cubes. In this way, we greatly generalize the result known for kinky benzenoid graphs. Finally, some open problems are also presented.
A function f:V(G)→{0,1,…,k} is called a k-rainbow independent dominating function of G if Vi={x∈V(G):f(x)=i} is independent for 1 ≤ i ≤ k, and for every x ∈ V0 it follows that N(x) ∩ Vi ≠ ∅, for ...every i ∈ k. The k-rainbow independent domination number, γrik(G), of a graph G is the minimum of w(f)=∑i=1k|Vi| over all such functions. In this paper we show that the problem of determining whether a graph has a k-rainbow independent dominating function of a given weight is NP-complete for bipartite graphs and that there exists a linear-time algorithm to compute γrik(G) of trees. In addition, sharp bounds for the k-rainbow independent domination number of the lexicographic product are presented, as well as the exact formula in the case k=2.
We obtain new results on the 2-rainbow domination number of generalized Petersen graphs P(ck,k). Exact values are established for all infinite families where the general lower bound 4/5ck is ...attained. In all other cases lower and upper bounds with small gaps are given.
PDF
