The characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. Finding efficient algorithms for computing characteristic polynomial of graphs is an active area of ...research and for some graph classes, like threshold graphs, there exist very fast algorithms which exploit combinatorial structure of the graphs. In this paper, we put forward some novel ideas based on divisor technique to obtain fast algorithms for computing the characteristic polynomial of threshold and chain graphs.
A set S of vertices of a graph G is a defensive alliance of G if for every v∈S, it holds |Nv∩S|≥|Nv−S|. An alliance is global if it is also a dominating set. The global defensive alliance number of G ...is the cardinality of a minimum global defensive alliance set of G. The lexicographic product of graphs Gn=(V1,E1) and Hm=(V2,E2) is the graph G=(V,E), such that V=V1×V2 and E={(u1,u2)(v1,v2):u1v1∈E1, or u1=v1 and u2v2∈E2}. In this paper, we determine the global defensive alliance number of the lexicographic product of paths and cycles.
Consider a simple connected graph
G
=
(
V
,
E
)
of order
p
and size
q
. For a bijection
f
:
E
→
{
1
,
2
,
…
,
q
}
, let
f
+
(
u
)
=
∑
e
∈
E
(
u
)
f
(
e
)
where
E
(
u
)
is the set of edges incident to
...u
. We say
f
is a local antimagic labeling of
G
if for any two adjacent vertices
u
and
v
, we have
f
+
(
u
)
≠
f
+
(
v
)
. The minimum number of distinct values of
f
+
taken over all local antimagic labeling of
G
is denoted by
χ
la
(
G
)
. Let
G
H
be the lexicographic product of graphs
G
and
H
. In this paper, we obtain sharp upper bound for
χ
la
(
G
O
n
)
where
O
n
is a null graph of order
n
≥
3
. Sufficient conditions for even regular bipartite and tripartite graphs
G
to have
χ
la
(
G
)
=
3
are also obtained. Consequently, we successfully determined the local antimagic chromatic number of infinitely many (connected and disconnected) regular graphs that partially support the existence of an
r
-regular graph
G
of order
p
such that (i)
χ
la
(
G
)
=
χ
(
G
)
=
k
, and (ii)
χ
la
(
G
)
=
χ
(
G
)
+
1
=
k
for each possible
r
,
p
,
k
.
Rainbow domination in the lexicographic product of graphs Šumenjak, Tadeja Kraner; Rall, Douglas F.; Tepeh, Aleksandra
Discrete Applied Mathematics,
September 2013, 2013-09-00, 20130901, Letnik:
161, Številka:
13-14
Journal Article
Recenzirano
Odprti dostop
A k-rainbow dominating function of a graph G is a map f from V(G) to the set of all subsets of {1,2,…,k} such that {1,…,k}=⋃u∈N(v)f(u) whenever v is a vertex with f(v)=0̸. The k-rainbow domination ...number of G is the invariant γrk(G), which is the minimum sum (over all the vertices of G) of the cardinalities of the subsets assigned by a k-rainbow dominating function. We focus on the 2-rainbow domination number of the lexicographic product of graphs and prove sharp lower and upper bounds for this number. In fact, we prove the exact value of γr2(G∘H) in terms of domination invariants of G except for the case when γr2(H)=3 and there exists a minimum 2-rainbow dominating function of H such that there is a vertex in H with the label {1,2}.
A linear k-forest of an undirected graph G is a subgraph of G whose components are paths with lengths at most k. The linear k-arboricity of G, denoted by lak(G), is the minimum number of linear ...k-forests needed to partition the edge set E(G) of G. In this paper, the exact values of the linear (n−1)-arboricity of lexicographic product graphs Kn ○ Kn, n and Kn, n ○ Kn are obtained. Furthermore, lak(Kn,n□Kn,n) are also derived for the Cartesian product graph of two copies of Kn, n. These results confirm the conjecture about the upper bound lak(G) given in Discrete Math. 41(1982)219-220 for Kn ○ Kn, n, Kn, n ○ Kn and Kn,n□Kn,n.
A set S ⊆ V (G) of an undirected graph G is a locating-dominating set of G if for each v ∈ V (G) \ S, there exists w ∈ S such tha vw ∈ E(G) and NG(x) ∩ S ̸= NG(y) ∩ S for any two distinct vertices x ...and y in V (G) \ S. S is a stable locating-dominating set of G if it is a locating-dominating set of G and S \ {v} is a locating-dominating set of G for each v ∈ S. The minimum cardinality of a stable locating-dominating set of G, denoted by γSLD(G), is called the stable locating-domination number of G. In this paper, we investigate this concept and the corresponding parameter for edge corona and lexicographic product of graphs.
Let G be a connected graph. A subset S ⊆ V (G) is a strong resolving dominating set of G if S is a dominating set and for every pair of vertices u, v ∈ V (G), there exists a vertex w ∈ S such that u ...∈ IGv, w or IGu, w. The smallest cardinality of a strong resolving dominating set of G is called the strong resolving domination number of G. In this paper, we characterize the strong resolving dominating sets in the lexicographic product of graphs and determine the corresponding resolving domination number.
An outer independent double Italian dominating function on a graph $G$ is a function $f:V(G)\rightarrow\{0,1,2,3\}$ for which each vertex $x\in V(G)$ with $\color{red}{f(x)\in \{0,1\}}$ then ...$\sum_{y\in Nx}f(y)\geqslant 3$ and vertices assigned $0$ under $f$ are independent. The outer independent double Italian domination number $\gamma_{oidI}(G)$ is the minimum weight of an outer independent double Italian dominating function of graph $G$. In this work, we present some contributions to the study of outer independent double Italian domination of three graph products. We characterize the Cartesian product, lexicographic product and direct product of custom graphs in terms of this parameter. We also provide the best possible upper and lower bounds for these three products for arbitrary graphs.
Weakened Gallai-Ramsey numbers Gabrielle Beam; Mark Budden
Surveys in mathematics and its applications,
08/2018, Letnik:
13 (2018)
Journal Article
Recenzirano
Odprti dostop
In the Ramsey theory of graphs, one seeks to determine the value of the Ramsey number rt(n), defined to be the least natural number p such that every coloring of the edges of Kp using t colors ...results in a monochromatic copy of Kn in some color. In this paper, we demonstrate the standard techniques used for finding bounds for Ramsey numbers by combining two standard generalizations of rt(n). First, we restrict our attention to Gallai colorings: those that avoid rainbow triangles. Within this setting, we then focus on finding subgraphs isomorphic to Kn that are spanned by edges using at most s ≤ t-1 colors. The resulting generalization of rt(n) is called a weakened Gallai-Ramsey number, denoted grst(n). As such, we determine several explicit small values and prove a few general properties of such numbers.
Let $ V(G) $ be the vertex set of a simple and connected graph $ G $. A subset $ S\subseteq V(G) $ is a distance-equalizer set of $ G $ if, for every pair of vertices $ u, v\in V(G)\setminus S $, ...there exists a vertex in $ S $ that is equidistant to $ u $ and $ v $. The minimum cardinality among the distance-equalizer sets of $ G $ is the equidistant dimension of $ G $, denoted by $ \xi(G) $. In this paper, we studied the problem of finding $ \xi(G\circ H) $, where $ G\circ H $ denotes the lexicographic product of two graphs $ G $ and $ H $. The aim was to express $ \xi(G\circ H) $ in terms of parameters of $ G $ and $ H $. In particular, we considered the cases in which $ G $ has a domination number equal to one, as well as the cases where $ G $ is a path or a cycle, among others. Furthermore, we showed that $ \xi(G)\le \xi(G\circ H)\le \xi(G)|V(H)| $ for every connected graph $ G $ and every graph $ H $ and we discussed the extreme cases. We also showed that the general problem of finding the equidistant dimension of a graph is NP-hard.
PDF
