Page 288 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 288
GRAPH POLYNOMIALS (MS-62)
Some new results on independent domination polynomial of a graph
Saeid Alikhani, alikhani206@gmail.com
Yazd University, Islamic Republic of Iran
Coauthor: Somayeh Jahari
An independent dominating set of the simple graph G = (V, E) is a vertex subset that is both
dominating and independent in G. The independent domination polynomial of a graph G is the
polynomial Di(G, x) = A x|A|, summed over all independent dominating subsets A ⊆ V . A
root of Di(G, x) is called an independence domination root. We first enumerate independent
dominating sets in several classes of graphs made by a linear or cyclic concatenation of basic
building blocks. Explicit recurrences are derived for the number of independent dominating
sets of these kind of graphs. We also investigate the independent domination polynomials of
some generalized compound graphs. As consequence, construct graphs whose independence
domination roots are real.
Normal Subgroup Based Power Graph of a Finite Group
Seyed Ali Reza Ashrafi Ghomroodi, ashrafi@kashanu.ac.ir
University of Kashan, Islamic Republic of Iran
Coauthor: Nasrin Malek-Mohammadi
Let G be a finite group and N ¢ G. The normal subgroup based power graph ΓN (G) is an
undirected graph with vertex set (G \ N ) ∪ {e} in which two distinct vertices a and b are
adjacent if and only if aN = bmN or bN = anN , for some positive integers m and n. In this
talk, we report on our recent results on the normal subgroup based power graph of a finite group.
As a consequence of this talk, a characterization of all pairs (G, N ) of a finite group G and a
proper non-trivial normal subgroup N of G such that ΓH(G) is split, bisplit or (n − 1)−bisplit
are given. Moreover, all finite groups G with c−cyclic normal subgroup based power graph,
c ≤ 4, will be determined.
Polynomial Approximation of the Number of Possible Final Positions of a
Random Walk for a Certain Class of Metric Digraphs
Vsevolod Chernyshev, vchernyshev@hse.ru
National Research University Higher School of Economics, Russian Federation
Let us consider a finite compact metric graph (see [1] and references therein), that is, a one-
dimensional CW complex and a random walk on it. The main unlikeness with the common
graph is that the final position of a walk can be any point on an edge of a metric graph, and
not only one of the vertices. Let one point start its move along the graph from a chosen vertex
at the initial moment of time. The passage time for each individual edge is fixed. In each
vertex, the point with some non-zero probability selects one of the outgoing edges for further
movement. Backward turns on the edges are prohibited in this model. Our aim is to analyze an
asymptotics of the number of possible final position of such random walk as time increases. The
only assumption about the probabilities of choosing an edge is that it is non-zero for all edges,
i.e. a situation of a general position. Such random walk could naturally arise while studying the
286
Some new results on independent domination polynomial of a graph
Saeid Alikhani, alikhani206@gmail.com
Yazd University, Islamic Republic of Iran
Coauthor: Somayeh Jahari
An independent dominating set of the simple graph G = (V, E) is a vertex subset that is both
dominating and independent in G. The independent domination polynomial of a graph G is the
polynomial Di(G, x) = A x|A|, summed over all independent dominating subsets A ⊆ V . A
root of Di(G, x) is called an independence domination root. We first enumerate independent
dominating sets in several classes of graphs made by a linear or cyclic concatenation of basic
building blocks. Explicit recurrences are derived for the number of independent dominating
sets of these kind of graphs. We also investigate the independent domination polynomials of
some generalized compound graphs. As consequence, construct graphs whose independence
domination roots are real.
Normal Subgroup Based Power Graph of a Finite Group
Seyed Ali Reza Ashrafi Ghomroodi, ashrafi@kashanu.ac.ir
University of Kashan, Islamic Republic of Iran
Coauthor: Nasrin Malek-Mohammadi
Let G be a finite group and N ¢ G. The normal subgroup based power graph ΓN (G) is an
undirected graph with vertex set (G \ N ) ∪ {e} in which two distinct vertices a and b are
adjacent if and only if aN = bmN or bN = anN , for some positive integers m and n. In this
talk, we report on our recent results on the normal subgroup based power graph of a finite group.
As a consequence of this talk, a characterization of all pairs (G, N ) of a finite group G and a
proper non-trivial normal subgroup N of G such that ΓH(G) is split, bisplit or (n − 1)−bisplit
are given. Moreover, all finite groups G with c−cyclic normal subgroup based power graph,
c ≤ 4, will be determined.
Polynomial Approximation of the Number of Possible Final Positions of a
Random Walk for a Certain Class of Metric Digraphs
Vsevolod Chernyshev, vchernyshev@hse.ru
National Research University Higher School of Economics, Russian Federation
Let us consider a finite compact metric graph (see [1] and references therein), that is, a one-
dimensional CW complex and a random walk on it. The main unlikeness with the common
graph is that the final position of a walk can be any point on an edge of a metric graph, and
not only one of the vertices. Let one point start its move along the graph from a chosen vertex
at the initial moment of time. The passage time for each individual edge is fixed. In each
vertex, the point with some non-zero probability selects one of the outgoing edges for further
movement. Backward turns on the edges are prohibited in this model. Our aim is to analyze an
asymptotics of the number of possible final position of such random walk as time increases. The
only assumption about the probabilities of choosing an edge is that it is non-zero for all edges,
i.e. a situation of a general position. Such random walk could naturally arise while studying the
286
