2020
5
1
0
81
On relation between the Kirchhoff index and number of spanning trees of graph
2
2
Let $G=(V,E)$, $V={1,2,ldots,n}$, $E={e_1,e_2,ldots,e_m}$,be a simple connected graph, with sequence of vertex degrees$Delta =d_1geq d_2geqcdotsgeq d_n=delta >0$ and Laplacian eigenvalues$mu_1geq mu_2geqcdotsgeqmu_{n1}>mu_n=0$. Denote by $Kf(G)=nsum_{i=1}^{n1}frac{1}{mu_i}$ and $t=t(G)=frac 1n prod_{i=1}^{n1} mu_i$ the Kirchhoff index and number of spanning trees of $G$, respectively. In this paper we determine several lower bounds for $Kf(G)$ depending on $t(G)$ and some of the graph parameters $n$, $m$, or $Delta$.
1

1
8


Igor
Milovanovic
Faculty of Electronic Engineering, Nis, Serbia
Faculty of Electronic Engineering, Nis, Serbia
Serbia
igor@elfak.ni.ac.rs


Edin
Glogic
State University of Novi Pazar, Novi Pazar, Serbia
State University of Novi Pazar, Novi Pazar,
Serbia
edin_gl@hotmail.com


Marjan
Matejic
Faculty of Electronic Engineering, Nis, Srbia
Faculty of Electronic Engineering, Nis, Srbia
Serbia
marjan.matejic@elfak.ni.ac.rs


Emina
Milovanovic
Faculty of Electronic Engineering, Nis, Serbia
Faculty of Electronic Engineering, Nis, Serbia
Serbia
ema@elfak.ni.ac.rs
Topological indices
Kirchhoff index
spanning trees
A study on some properties of leap graphs
2
2
In a graph G, the first and second degrees of a vertex v is equal to thenumber of their first and second neighbors and are denoted by d(v/G) andd 2 (v/G), respectively. The first, second and third leap Zagreb indices are thesum of squares of second degrees of vertices of G, the sum of products of second degrees of pairs of adjacent vertices in G and the sum of products of firstand second degrees of vertices of G, respectively. In this paper, we initiate in studying a new class of graphs depending on the relationship between firstand second degrees of vertices and is socalled a leap graph. Some propertiesof the leap graphs are presented. All leap trees and {C 3, C 4 }free leap graphsare characterized.
1

9
17


Ahmed
Naji
Department of Mathematics, University of Mysore, Mysusu, India
Department of Mathematics, University of
India
ama.mohsen78@gmail.com


B.
Davvaz
Department of Mathematics, Yazd University, Yazd, Iran
Department of Mathematics, Yazd University,
Iran
davvaz@yazd.co.ir


Sultan S.
Mahde
Department of Studies in Mathematics, University of Mysore, Manasagangotri, Mysore  570 006, India
Department of Studies in Mathematics, University
India
sultan.mahde@gmail.com


N.D.
Soner
Department of Studies in Mathematics, University of Mysore, Manasagangotri, Mysore  570 006, India
Department of Studies in Mathematics, University
India
ndsoner@yahoo.com.in
Distancedegrees (of vertices)
leap Zagreb indices
leap graphs
A note on the Roman domatic number of a digraph
2
2
Roman dominating function} on a digraph $D$ with vertex set $V(D)$ is a labeling$fcolon V(D)to {0, 1, 2}$such that every vertex with label $0$ has an inneighbor with label $2$. A set ${f_1,f_2,ldots,f_d}$ ofRoman dominating functions on $D$ with the property that $sum_{i=1}^d f_i(v)le 2$ for each $vin V(D)$,is called a {em Roman dominating family} (of functions) on $D$. The maximum number of functions in aRoman dominating family on $D$ is the {em Roman domatic number} of $D$, denoted by $d_{R}(D)$.In this note, we study the Roman domatic number in digraphs, and we present some sharpbounds for $d_{R}(D)$. In addition, we determine the Roman domatic number of some digraphs.Some of our results are extensions of wellknown properties of the Roman domatic number ofundirected graphs.
1

19
26


Lutz
Volkmann
RWTH Aachen University
RWTH Aachen University
Germany
volkm@math2.rwthaachen.de


D.
Meierling
RWTH Aachen University
RWTH Aachen University
Germany
meierling@math2.rwthaachen.de
Digraphs
Roman dominating function
Roman domination number
Roman domatic number
Total double Roman domination in graphs
2
2
Let $G$ be a simple graph with vertex set $V$. A double Roman dominating function (DRDF) on $G$ is a function $f:Vrightarrow{0,1,2,3}$ satisfying that if $f(v)=0$, then the vertex $v$ must be adjacent to at least two vertices assigned $2$ or one vertex assigned $3$ under $f$, whereas if $f(v)=1$, then the vertex $v$ must be adjacent to at least one vertex assigned $2$ or $3$. The weight of a DRDF $f$ is the sum $sum_{vin V}f(v)$. A total double Roman dominating function (TDRDF) on a graph $G$ with no isolated vertex is a DRDF $f$ on $G$ with the additional property that the subgraph of $G$ induced by the set ${vin V:f(v)ne0}$ has no isolated vertices. The total double Roman domination number $gamma_{tdR}(G)$ is the minimum weight of a TDRDF on $G$. In this paper, we give several relations between the total double Roman domination number of a graph and other domination parameters and we determine the total double Roman domination number of some classes of graphs.
1

27
39


Guoliang
Hao
College of Science, East China University of Technology, Nanchang, P. R. China
College of Science, East China University
China
guolianghao@163.com


Lutz
Volkmann
RWTH Aachen University
RWTH Aachen University
Germany
volkm@math2.rwthaachen.de


Doost Ali
Mojdeh
University of Mazandaran
University of Mazandaran
Iran
damojdeh@umz.ac.ir
total double Roman domination
double Roman domination
total Roman domination
total domination
domination
On the edge geodetic and edge geodetic domination numbers of a graph
2
2
In this paper, we study both concepts of geodetic dominatingand edge geodetic dominating sets and derive some tight upper bounds onthe edge geodetic and the edge geodetic domination numbers. We also obtainattainable upper bounds on the maximum number of elements in a partitionof a vertex set of a connected graph into geodetic sets, edge geodetic sets,geodetic dominating sets and edge geodetic dominating sets, respectively.
1

41
54


Vladimir
Samodivkin
University of Architecture, Civil Еngineering and Geodesy;
Department of Mathematics
University of Architecture, Civil Еngineering
Bulgaria
vl.samodivkin@gmail.com
Domination number
(edge) geodetic number
(edge) geodetic domination number
The topological ordering of covering nodes
2
2
The topological ordering algorithm sorts nodes of a directed graph such that the order of the tail of each arc is lower than the order of its head. In this paper, we introduce the notion of covering between nodes of a directed graph. Then, we apply the topological orderingalgorithm on graphs containing the covering nodes. We show that there exists a cut set withforward arcs in these graphs and the order of the covering nodes is successive.
1

55
60


Gholam Hassan
Shirdel
University of Qom
University of Qom
Iran
shirdel81math@gmail.com


Nasrin
Kahkeshani
University of Qom
University of Qom
Iran
nasrinkahkeshani@gmail.com
Directed graph
Covering nodes
Topological ordering algorithm
Characterization of signed paths and cycles admitting minus dominating function
2
2
If G = (V, E, σ) is a finite signed graph, a function f : V → {−1, 0, 1} is a minusdominating function (MDF) of G if f(u) +summation over all vertices v∈N(u) of σ(uv)f(v) ≥ 1 for all u ∈ V . In this paper we characterize signed paths and cycles admitting an MDF.
1

61
68


Mayamma
Joseph
Department of Mathematics, CHRIST (Deemed to be University), Bangalore29, INDIA
Department of Mathematics, CHRIST (Deemed
India
mayamma.joseph@christuniversity.in


S.R.
Shreyas
Department of Mathematics, CHRIST (Deemed to be University), Bangalore29, INDIA
Department of Mathematics, CHRIST (Deemed
India
Signed graphs
Minus domination
Minus Dominating Function
The 2dimension of a Tree
2
2
Let $x$ and $y$ be two distinct vertices in a connected graph $G$. The $x,y$location of a vertex $w$ is the ordered pair of distances from $w$ to $x$ and $y$, that is, the ordered pair $(d(x,w), d(y,w))$. A set of vertices $W$ in $G$ is $x,y$located if any two vertices in $W$ have distinct $x,y$location.A set $W$ of vertices in $G$ is 2located if it is $x,y$located, for some distinct vertices $x$ and $y$. The 2dimension of $G$ is the order of a largest set that is 2located in $G$. Note that this notion is related to the metric dimension of a graph, but not identical to it.We study in depth the trees $T$ that have a 2locating set, that is, have 2dimension equal to the order of $T$. Using these results, we have a nice characterization of the 2dimension of arbitrary trees.
1

69
81


Jason
Hedetniemi
Department of Mathematics
Wingate University
Wingate NC
USA
Department of Mathematics
Wingate University
Winga
United States
jason.hedetniemi@gmail.com


Stephen
Hedetniemi
School of Computing
Clemson University
Clemson, SC
U.S.A.
School of Computing
Clemson University
Clemson,
United States
hedet@cs.clemson.edu


Renu C.
Renu C. Laskar
Clemson University
Clemson University
United States
rclsk@clemson.edu


Henry Martyn
Mulder
Econometrisch Instituut
Erasmus Universiteit
Rotterdam
Netherlands
Econometrisch Instituut
Erasmus Universiteit
Rot
Netherlands
hmmulder@ese.eur.nl
resolvability
location number
2dimension
tree
2locating set