Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
5
1
2020
06
01
On relation between the Kirchhoff index and number of spanning trees of graph
1
8
EN
Igor
Milovanovic
Faculty of Electronic Engineering, Nis, Serbia
igor@elfak.ni.ac.rs
Edin
Glogic
State University of Novi Pazar, Novi Pazar, Serbia
edin_gl@hotmail.com
Marjan
Matejic
Faculty of Electronic Engineering, Nis, Srbia
marjan.matejic@elfak.ni.ac.rs
Emina
Milovanovic
Faculty of Electronic Engineering, Nis, Serbia
ema@elfak.ni.ac.rs
10.22049/cco.2019.26270.1088
Let $G$ be a simple connected graph with degree sequence $(d_1,d_2,\ldots, d_n)$ where $\Delta =d_1\geq d_2\geq\cdots\geq d_n=\delta >0$ and let $\mu_1\geq \mu_2\geq\cdots\geq\mu_{n-1}>\mu_n=0$ be the Laplacian eigenvalues of $G$. Let $Kf(G)=n\sum_{i=1}^{n-1} \frac{1}{\mu_i}$ and $\tau(G)=\frac 1n \prod_{i=1}^{n-1} \mu_i$ denote the Kirchhoff index and the number of spanning trees of $G$, respectively. In this paper we establish several lower bounds for $Kf(G)$ in terms of $\tau(G)$, the order, the size and maximum degree of $G$.
Topological indices,Kirchhoff index,spanning trees
http://comb-opt.azaruniv.ac.ir/article_13873.html
http://comb-opt.azaruniv.ac.ir/article_13873_db13742154db832474287f8d4db11c5f.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
5
1
2020
06
01
A study on some properties of leap graphs
9
17
EN
Ahmed
M
Naji
0000-0003-0007-8927
Department of Mathematics, University of Mysore, Mysusu, India
ama.mohsen78@gmail.com
B.
Davvaz
Department of Mathematics, Yazd University, Yazd, Iran
davvaz@yazd.co.ir
Sultan S.
Mahde
Department of Studies in Mathematics, University of Mysore, Manasagangotri, Mysore - 570 006, India
sultan.mahde@gmail.com
N.D.
Soner
Department of Studies in Mathematics, University of Mysore, Manasagangotri, Mysore - 570 006, India
ndsoner@yahoo.com.in
10.22049/cco.2019.26430.1108
In a graph $G$, the first and second degrees of a vertex $v$ are equal to the number of their first and second neighbors and are denoted by $d(v/G)$ and $d_2(v/G)$, respectively. The first, second and third leap Zagreb indices are the sum 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 first and second degrees of vertices of $G$, respectively. In this paper, we initiate in studying a new class of graphs depending on the relationship between first and second degrees of vertices and is so-called a leap graph. Some properties of the leap graphs are presented. All leap trees and $\{C_3, C_4\}$-free leap graphs are characterized.
Distance-degrees (of vertices),leap Zagreb indices,leap graphs
http://comb-opt.azaruniv.ac.ir/article_13876.html
http://comb-opt.azaruniv.ac.ir/article_13876_3e34a313e1c9a12cdfc1edc950e25098.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
5
1
2020
06
01
A note on the Roman domatic number of a digraph
19
26
EN
Lutz
Volkmann
0000-0003-3496-277X
RWTH Aachen University
volkm@math2.rwth-aachen.de
D.
Meierling
RWTH Aachen University
meierling@math2.rwth-aachen.de
10.22049/cco.2019.26419.1107
A Roman dominating function on a digraph $D$ with vertex set $V(D)$ is a labeling $f\colon V(D)\to \{0, 1, 2\}$ such that every vertex with label $0$ has an in-neighbor with label $2$. A set $\{f_1,f_2,\ldots,f_d\}$ of Roman dominating functions on $D$ with the property that $\sum_{i=1}^d f_i(v)\le 2$ for each $v\in V(D)$, is called a Roman dominating family (of functions) on $D$. The maximum number of functions in a Roman dominating family on $D$ is the 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 sharp bounds for $d_{R}(D)$. In addition, we determine the Roman domatic number of some digraphs. Some of our results are extensions of well-known properties of the Roman domatic number of undirected graphs.
Digraphs,Roman dominating function,Roman domination number,Roman domatic number
http://comb-opt.azaruniv.ac.ir/article_13884.html
http://comb-opt.azaruniv.ac.ir/article_13884_bf374c8fd79d776bfc11bd95660ff3b1.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
5
1
2020
06
01
Total double Roman domination in graphs
27
39
EN
Guoliang
Hao
College of Science, East China University of Technology, Nanchang, P. R. China
guoliang-hao@163.com
Lutz
Volkmann
0000-0003-3496-277X
RWTH Aachen University
volkm@math2.rwth-aachen.de
Doost Ali
Mojdeh
0000-0001-9373-3390
University of Mazandaran
damojdeh@umz.ac.ir
10.22049/cco.2019.26484.1118
Let $G$ be a simple graph with vertex set $V$. A double Roman dominating function (DRDF) on $G$ is a function $f:V\rightarrow\{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_{v\in 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 $\{v\in 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.
total double Roman domination,double Roman domination,total Roman domination,total domination,domination
http://comb-opt.azaruniv.ac.ir/article_13945.html
http://comb-opt.azaruniv.ac.ir/article_13945_dce686282b94fcb96a05edec316a45ef.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
5
1
2020
06
01
On the edge geodetic and edge geodetic domination numbers of a graph
41
54
EN
Vladimir
Samodivkin
0000-0001-7934-5789
University of Architecture, Civil Еngineering and Geodesy;
Department of Mathematics
vl.samodivkin@gmail.com
10.22049/cco.2019.26347.1099
In this paper, we study both concepts of geodetic dominating and edge geodetic dominating sets and derive some tight upper bounds on the edge geodetic and the edge geodetic domination numbers. We also obtain attainable upper bounds on the maximum number of elements in a partition of a vertex set of a connected graph into geodetic sets, edge geodetic sets, geodetic dominating sets and edge geodetic dominating sets, respectively.
Domination number,(edge) geodetic number,(edge) geodetic domination number
http://comb-opt.azaruniv.ac.ir/article_13946.html
http://comb-opt.azaruniv.ac.ir/article_13946_a04e695bc31f9c7d591a19cbb7f8733e.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
5
1
2020
06
01
The topological ordering of covering nodes
55
60
EN
Gholam Hassan
Shirdel
0000000327594606
University of Qom
shirdel81math@gmail.com
Nasrin
Kahkeshani
University of Qom
nasrinkahkeshani@gmail.com
10.22049/cco.2019.26119.1077
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 ordering algorithm on graphs containing the covering nodes. We show that there exists a cut set with forward arcs in these graphs and the order of the covering nodes is successive.
Directed graph,Covering nodes,Topological ordering algorithm
http://comb-opt.azaruniv.ac.ir/article_13958.html
http://comb-opt.azaruniv.ac.ir/article_13958_bb278a35f5e754d8fa7152e537a20961.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
5
1
2020
06
01
Characterization of signed paths and cycles admitting minus dominating function
61
68
EN
Mayamma
Joseph
0000-0001-5819-247X
Department of Mathematics, CHRIST (Deemed to be University), Bangalore-29, INDIA
mayamma.joseph@christuniversity.in
S.R.
Shreyas
Department of Mathematics, CHRIST (Deemed to be University), Bangalore-29, INDIA
10.22049/cco.2019.26661.1128
Let $G=(V,E,\sigma)$ be a finite signed graph. A function $f: V \rightarrow\{-1,0,1\}$ is a minus dominating function (MDF) of $ G $ if $f(u)+\sum_{v \in N(u)} \sigma (uv)f(v)\geq 1 $ for all $ u\in V $. In this paper we characterize signed paths and cycles admitting an MDF.
Signed graphs,Minus domination,Minus Dominating Function
http://comb-opt.azaruniv.ac.ir/article_13977.html
http://comb-opt.azaruniv.ac.ir/article_13977_d69f8161a1b3221a35ffcfac6d8735d5.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
5
1
2020
06
01
The 2-dimension of a Tree
69
81
EN
Jason
Hedetniemi
Department of Mathematics
Wingate University
Wingate NC
USA
jason.hedetniemi@gmail.com
Stephen
Hedetniemi
School of Computing
Clemson University
Clemson, SC
U.S.A.
hedet@cs.clemson.edu
Renu C.
Renu C. Laskar
Clemson University
rclsk@clemson.edu
Henry Martyn
Mulder
0000-0002-4776-4046
Econometrisch Instituut
Erasmus Universiteit
Rotterdam
Netherlands
hmmulder@ese.eur.nl
10.22049/cco.2019.26495.1119
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$-locations. A set $W$ of vertices in $G$ is 2-located if it is $x,y$-located, for some distinct vertices $x$ and $y$. The 2-dimension of $G$ is the order of a largest set that is 2-located 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 2-locating set, that is, have 2-dimension equal to the order of $T$. Using these results, we have a nice characterization of the 2-dimension of arbitrary trees.
resolvability,location number,2-dimension,tree,2-locating set
http://comb-opt.azaruniv.ac.ir/article_13979.html
http://comb-opt.azaruniv.ac.ir/article_13979_67e6ec33d043a864ea37af1094c77ac3.pdf