CONNECTED DOMINATION GAME Irsic, Vesna
Applicable analysis and discrete mathematics,
2022, Letnik:
16, Številka:
1
Journal Article
Recenzirano
Odprti dostop
The connected domination game was introduced in 2019 by Borowiecki, Fiedorowicz and Sidorowicz as another variation of the domination game. We answer a problem from their paper regarding the relation ...between the number of moves in a game where Dominator/Staller starts the game. Additionally, we study the relation to the diameter and present graphs with small game connected domination number. We also determine the value on the lexicographic products, and consider the effect of predomination of a vertex.
Lexicographic product graphs are antimagic Ma, Wenhui; Dong, Guanghua; Lu, Yingyu ...
AKCE International Journal of Graphs and Combinatorics,
12/1/2018, 2018-12-01, Letnik:
15, Številka:
3
Journal Article
Recenzirano
Odprti dostop
A graph with
edges is called
if its edges can be labeled with 1, 2,
,
such that the sums of the labels on the edges incident to each vertex are distinct. Hartsfield and Ringel conjectured that every ...connected graph other than
is antimagic. In this paper, through a labeling method and a modification on this labeling, we obtained that the lexicographic product graphs
are antimagic.
Edge Metric Dimension of Some Graph Operations Peterin, Iztok; Yero, Ismael G.
Bulletin of the Malaysian Mathematical Sciences Society,
05/2020, Letnik:
43, Številka:
3
Journal Article
Recenzirano
Odprti dostop
Let
G
=
(
V
,
E
)
be a connected graph. Given a vertex
v
∈
V
and an edge
e
=
u
w
∈
E
, the distance between
v
and
e
is defined as
d
G
(
e
,
v
)
=
min
{
d
G
(
u
,
v
)
,
d
G
(
w
,
v
)
}
. A nonempty ...set
S
⊂
V
is an edge metric generator for
G
if for any two edges
e
1
,
e
2
∈
E
there is a vertex
w
∈
S
such that
d
G
(
w
,
e
1
)
≠
d
G
(
w
,
e
2
)
. The minimum cardinality of any edge metric generator for a graph
G
is the edge metric dimension of
G
. The edge metric dimension of the join, lexicographic, and corona product of graphs is studied in this article.
The neighbourhood of a vertex v of a graph G is the set N(v) of all vertices adjacent to v in G. For D⊆V(G) we define D¯=V(G)∖D. A set D⊆V(G) is called a super dominating set if for every vertex ...u∈D¯, there exists v∈D such that N(v)∩D¯={u}. The super domination number of G is the minimum cardinality among all super dominating sets in G. In this article we obtain closed formulas and tight bounds for the super dominating number of lexicographic product graphs in terms of invariants of the factor graphs involved in the product. As a consequence of the study, we show that the problem of finding the super domination number of a graph is NP-Hard.
For a (molecular) graph, the first Zagreb index M1 is the sum of squares of the degrees of vertices, and the second Zagreb index M2 is the sum of the products of the degrees of pairs of adjacent ...vertices. In this work, we study the first and second Zagreb indices of graphs based on four new operations related to the lexicographic product, subdivision and total graph.
A total Roman dominating function of a graph G=(V,E) is a function f:V(G)→{0,1,2} such that for every vertex v with f(v)=0 there exists a vertex u adjacent to v with f(u)=2, and such that the ...subgraph induced by the set of vertices labeled one or two has no isolated vertices. The total Roman domination number of G is the minimum value of the sums ∑v∈Vf(v) over all total Roman dominating functions f of G. In this paper we study the total Roman domination number of the lexicographic product of graphs.
Lexicographic product graphs Pm[Pn] are antimagic Ma, Wenhui; Dong, Guanghua; Lu, Yingyu ...
AKCE International Journal of Graphs and Combinatorics,
December 2018, 2018-12-01, Letnik:
15, Številka:
3
Journal Article
Recenzirano
Odprti dostop
A graph with q edges is called antimagic if its edges can be labeled with 1, 2, …, q such that the sums of the labels on the edges incident to each vertex are distinct. Hartsfield and Ringel ...conjectured that every connected graph other than K2 is antimagic. In this paper, through a labeling method and a modification on this labeling, we obtained that the lexicographic product graphs PmPn are antimagic.
Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the ...second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph G (regardless of Ben’s strategy) is called the indicated chromatic number of G, denoted by χi(G). In this paper, we show that for any graphs G and H, GH is k-indicated colorable for all k≥col(G)col(H). Also, we show that for any graph G and for some classes of graphs H with χ(H)=χi(H)=ℓ, GH is k-indicated colorable if and only if GKℓ is k-indicated colorable. As a consequence of this result, we show that if G∈G={Chordal graphs, Cographs, Complement of bipartite graphs, {P5,C4}-free graphs, Connected {P6,C5,P5¯,K1,3}-free graphs which contain an induced C6, Complete multipartite graphs} and H∈F={Bipartite graphs, Chordal graphs, Cographs, {P5,K3}-free graphs, {P5,paw}-free graphs, Complement of bipartite graphs, {P5,K4,kite,bull}-free graphs, Connected {P6,C5,P5¯,K1,3}-free graphs which contain an induced C6, {P5,C4}-free graphs, KC5(m1,m2,…,m5), Connected {P5,P2∪P3¯,P5¯,dart}-free graphs which contain an induced C5}, then GH is k-indicated colorable for every k≥χ(GH). This serves as a partial answer to one of the questions raised by A. Grzesik in Grzesik (2012). In addition, if G∈{Bipartite graphs, {P5,K3}-free graphs, {P5,paw}-free graphs} and H∈F, then we show that χi(GH)=χ(GH).
In a graph G, a vertex dominates itself and its neighbours. A subset S⊆V(G) is said to be a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality among ...all double dominating sets of G is the double domination number. In this article, we obtain tight bounds and closed formulas for the double domination number of lexicographic product graphs G∘H in terms of invariants of the factor graphs G and H.