In this paper, we consider when a lexicographic product of GO-spaces is Lindelöf. We mainly prove: (1) Let γ be any ordinal. Assume that for each α<γ, Xα is a Lindelöf GO-space, and for each α≥1, Xα ...has a minimum mα and maximum Mα. Then the lexicographic product ∏α<γXα of GO-spaces is also Lindelöf. (2) Let γ≤ω1. Assume that for each α<γ, Xα is a Lindelöf subspace of an ordinal. Then the lexicographic product ∏α<γXα of GO-spaces is also Lindelöf.
For a set W of vertices and a vertex v in a connected graph G, the k-vector rW(v)=(d(v,w1),…,d(v,wk)) is the metric representation of v with respect to W, where W={w1,…,wk} and d(x,y) is the distance ...between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct metric representations with respect to W. The minimum cardinality of a resolving set for G is its metric dimension. In this paper, we study the metric dimension of the lexicographic product of graphs G and H, denoted by GH. First, we introduce a new parameter, the adjacency dimension, of a graph. Then we obtain the metric dimension of GH in terms of the order of G and the adjacency dimension of H.
For two graphs
$ G_1 $
G
1
and
$ G_2 $
G
2
. Let
$ \mathcal {B} $
B
be a set of non-zero binary 2-tuples, i.e.
$ \mathcal {B}\subseteq \{0,1\}^{2}\setminus \{(0,0)\} $
B
⊆
{
0
,
1
}
2
∖
{
(
0
,
0
)
}
.... The NEPS (non-complete extended p-sum) of graphs
$ G_1,G_2 $
G
1
,
G
2
with basis
$ \mathcal {B} $
B
is denoted by NEPS
$ (G_1, G_2; \mathcal {B}) $
(
G
1
,
G
2
;
B
)
. Let
$ G_1G_2 $
G
1
G
2
be the lexicographic product of
$ G_1 $
G
1
and
$ G_2 $
G
2
. In this paper, we determine the spectra of the graph
$ G_0\blacksquare _{k_1} $
G
0
◼
k
1
NEPS
$ (G_1,G_{2}; \mathcal {B}) $
(
G
1
,
G
2
;
B
)
and
$ G_0\blacksquare _{k_1}G_1G_2 $
G
0
◼
k
1
G
1
G
2
with regular graphs
$ G_0 $
G
0
,
$ G_2 $
G
2
and an arbitrary graph
$ G_1 $
G
1
in terms of their spectra. As applications, the results on spectra enable us to construct some new cospectral graphs and integral spectrum graphs.
A set of vertices Wresolves a graph G if every vertex is uniquely determined by its coordinate of distances to the vertices in W. The minimum cardinality of a resolving set of G is called the metric ...dimension of G. In this paper, we consider a graph which is obtained by the lexicographic product between two graphs. The lexicographic product of graphs G and H, which is denoted by G∘H, is the graph with vertex set V(G)×V(H)={(a,v)|a∈V(G),v∈V(H)}, where (a,v) is adjacent to (b,w) whenever ab∈E(G), or a=b and vw∈E(H). We give the general bounds of the metric dimension of a lexicographic product of any connected graph G and an arbitrary graph H. We also show that the bounds are sharp.
Abstract
In this paper, we introduce the notion of Pythagorean Anti fuzzy graph. We then define the Cartesian product and Lexicographic product on Pythagorean Anti fuzzy graph. It is proved that ...Cartesian product of two Pythagorean Anti fuzzy graphs is Pythagorean Anti fuzzy graph and Lexicographic product of two Pythagorean Anti fuzzy graphs is Pythagorean Anti fuzzy graph. In general, Cartesian product and lexicographic product of two regular Pythagorean Anti fuzzy graphs need not be Pythagorean Anti fuzzy graph. Necessary and sufficient conditions for Cartesian and lexicographic product of two Pythagorean Anti fuzzy graphs to be regular are determined. Further, we define the concept of isomorphism on Pythagorean Anti fuzzy graph with suitable example.
A vertex v of a graph G=(V,E) is said to be undefended with respect to a function f:V⟶{0,1,2} if f(v)=0 and f(u)=0 for every vertex u adjacent to v. We call the function f a weak Roman dominating ...function if for every v such that f(v)=0 there exists a vertex u adjacent to v such that f(u)∈{1,2} and the function f′:V⟶{0,1,2} defined by f′(v)=1, f′(u)=f(u)−1 and f′(z)=f(z) for every z∈V∖{u,v}, has no undefended vertices. The weight of f is w(f)=∑v∈V(G)f(v). The weak Roman domination number of a graph G, denoted by γr(G), is the minimum weight among all weak Roman dominating functions on G. Henning and Hedetniemi (2003) showed that the problem of computing γr(G) is NP-Hard, even when restricted to bipartite or chordal graphs. This suggests finding γr(G) for special classes of graphs or obtaining good bounds on this invariant. In this article, we obtain closed formulae and tight bounds for the weak Roman domination number of lexicographic product graphs in terms of invariants of the factor graphs involved in the product.
A total coloring of a graph G is an assignment of colors to the elements of the graph G such that no two adjacent or incident elements receive the same color. The total chromatic number of a graph G, ...denoted by χ ″ ( G ) , is the minimum number of colors that suffice in a total coloring. Behzad and Vizing conjectured that for any graph G, Δ ( G ) + 1 ≤ χ ″ ( G ) ≤ Δ ( G ) + 2 , where Δ ( G ) is the maximum degree of G. In this paper, we prove the total coloring conjecture for certain classes of graphs of deleted lexicographic product, line graph and double graph.
Hop Dominating Sets in Graphs Under Binary Operations Canoy, Jr, Sergio; Mollejon, Reynaldo Villarobe; Canoy, John Gabriel E.
European journal of pure and applied mathematics,
01/2019, Letnik:
12, Številka:
4
Journal Article
Recenzirano
Odprti dostop
Let G be a (simple) connected graph with vertex and edge sets V (G) and E(G),respectively. A set S ⊆ V (G) is a hop dominating set of G if for each v ∈ V (G) \ S, there exists w ∈ S such that ...dG(v, w) = 2. The minimum cardinality of a hop dominating set of G, denoted by γh(G), is called the hop domination number of G. In this paper we revisit the concept of hop domination, relate it with other domination concepts, and investigate it in graphs resulting from some binary operations.
An edge-coloring of a graph $ G $ is an assignment of colors to its edges so that no two edges incident to the same vertex receive the same color. The chromatic index of $ G $, denoted by $ \chi'(G) ...$, is the least $ k $ for which $ G $ has a $ k $ edge-coloring. Graphs with $ \chi'(G) = \Delta(G) $ are said to be Class 1, and graphs with $ \chi'(G) = \Delta(G)+1 $ are said to be Class 2. Let $ G $ be a graph with $ V(G) = \{t_1, t_2, \ldots, t_n\} $, $ n\geq2 $, and $ h_n = (H_i)_{i\in\{1, 2, \ldots, n\}} $ be a sequence of vertex-disjoint graphs with $ V(H_i) = \{(t_i, y_1), (t_i, y_2), \ldots, (t_i, y_{m_i})\} $, $ m_i\geq1 $. The generalized lexicographic product $ Gh_n $ of $ G $ and $ h_n = (H_i)_{i\in\{1, 2, \ldots, n\}} $ is a simple graph with vertex set $ \bigcup_{i = 1}^{n}V(H_i) $, in which $ (t_i, y_p) $ is adjacent to $ (t_j, y_q) $ if and only if either $ t_i = t_j $ and $ (t_i, y_p)(t_i, y_q)\in E(H_i) $ or $ t_it_j\in E(G) $. If $ G $ is a complete graph with order 2, then $ Gh_2 $ denotes a join $ H_1+H_2 $ of vertex-disjoint graphs $ H_1 $ and $ H_2 $. If $ H_i\cong H $ for $ i = 1, 2, \ldots, n $, then $ Gh_n = GH $, where $ GH $ denotes the lexicographic product of two graphs $ G $ and $ H $. In this paper, we provide sufficient conditions for the generalized lexicographic product $ Gh_n $ of $ G $ and $ h_n = (H_i)_{i\in\{1, 2, \ldots, n\}} $ to be Class 1, where all graphs in $ h_n $ have the same number of vertices.
Let G be a graph of minimum degree at least two. A set D ⊆ V(G) is said to be a double total dominating set of G if |N (v) ∩ D| ≥ 2 for every vertex v ∈ V(G). The double total domination number of G, ...denoted by γ
×2,t
(G), is the minimum cardinality among all double total dominating sets of G. In this paper, we study this parameter for any generalized lexicographic product graph
. In particular, we show that
, where
represents the total {2}-domination number of
. Moreover, we obtain tight bounds and closed formulas on the double total domination number of this specific product of graphs in terms of domination invariants of the factor graphs. Finally, we characterize the graphs
for which
takes small values.