A general position set of a graph G is a set of vertices S in G such that no three vertices from S lie on a common shortest path. In this paper we introduce and study the general position achievement ...game. The game is played on a graph G by players A and B who alternatively pick vertices of G. A selection of a vertex is legal if has not been selected before and the set of vertices selected so far forms a general position set of G. The player who selects the last vertex wins the game. Playable vertices at each step of the game are described, and sufficient conditions for each of the players to win is given. The game is studied on Cartesian and lexicographic products. Among other results it is proved that A wins the game on Kn□Km if and only if both n and m are odd, and that B wins the game on G∘Kn if and only if either B wins on G or n is even.
The matching preclusion number of a graph, introduced in 2 as a fault analysis, is the minimum number of edges whose deletion leaves a resulting graph that has neither perfect matchings nor almost ...perfect matchings. As a generalization, Liu and Liu 14 recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number of graph is the minimum number of edges whose deletion results in a graph that has no fractional perfect matching. If the sets of edges of the graph attaining the minimum are precisely those incident to a single vertex of minimum degree, we say such graph is fractional super matched. In this paper, the upper and lower bounds for the fractional matching preclusion number for Cartesian product, direct product, strong product, and lexicographic product are obtained, and we give sufficient conditions for such graphs to be fractional super matched.
For two digraphs D=(V1,A1) and H=(V2,A2), the lexicographic product digraph DH is the digraph with vertex set V1 × V2. There is an arc from vertex (x1, y1) to vertex (x2, y2) in DH if and only if ...either x1x2 ∈ A1 or x1=x2 and y1y2 ∈ A2. The minimum degree and the arc-connectivity of D are denoted by δ(D) and λ(D), respectively. We prove that for any two digraphs D and H, λ(DH)≥min{n(t+λ(D)−δ(D)−1)+δ(DH),n2λ(D)} holds for any t≤min{δ(D)−λ(D)+1,λ(D)+1,n−1}, where n=|V(H)|. As a consequence, λ(DH)≥n(λ(D)−δ(D))+δ(DH). We also provide some sufficient conditions for DH to have maximum reliability with respected the connectedness and super connectedness.
In this paper we begin an exploration of several domination-related parameters (among which are the total, restrained, total restrained, paired, outer connected and total outer connected domination ...numbers) in the generalized lexicographic product (GLP for short) of graphs. We prove that for each GLP of graphs there exist several equality chains containing these parameters. Some known results on standard lexicographic product of two graphs are generalized or/and extended. We also obtain results on well μ-dominated GLP of graphs, where μ stands for any of the above mentioned domination parameters. In particular, we present a characterization of well μ-dominated GLP of graphs in the cases when μ is the domination number or the total domination number.
2-Locating Sets in a Graph Canete, Gymaima; Rara, Helen; Mahistrado, Angelica Mae
European journal of pure and applied mathematics,
07/2023, Letnik:
16, Številka:
3
Journal Article
Recenzirano
Odprti dostop
Let $G$ be an undirected graph with vertex-set $V(G)$ and edge-set $E(G)$, respectively. A set $S\subseteq V(G)$ is a $2$-locating set of $G$ if $\big|\big(N_G(x)\backslash N_G(y)\big)\cap S \cup ...\big(N_G(y)\backslash N_G(x)\big)\cap S\big|\geq 2$, for all \linebreak $x,y\in V(G)\backslash S$ with $x\neq y$, and for all $v\in S$ and $w\in V(G)\backslash S$, $\big(N_G(v)\backslash N_G(w)\big)\cap S \neq \varnothing$ or $\big(N_G(w)\backslash N_Gv\big) \cap S\neq \varnothing$. In this paper, we investigate the concept and study 2-locating sets in graphs resulting from some binary operations. Specifically, we characterize the 2-locating sets in the join, corona, edge corona and lexicographic product of graphs, and determine bounds or exact values of the 2-locating number of each of these graphs.
Total Protection of Lexicographic Product Graphs Martínez, Abel Cabrera; Rodríguez-Velázquez, Juan Alberto
Discussiones Mathematicae. Graph Theory,
08/2022, Letnik:
42, Številka:
3
Journal Article
Recenzirano
Odprti dostop
Given a graph
with vertex set
(
), a function
:
(
) → {0, 1, 2} is said to be a total dominating function if Σ
)
0 for every
∈
(
), where
) denotes the open neighbourhood of
. Let
= {
∈
(
) :
) =
}. ...A total dominating function
is a total weak Roman dominating function if for every vertex
∈
there exists a vertex
∈
) ∩ (
∪
) such that the function
′, defined by
′(
) = 1,
′(
) =
) − 1 and
′(
) =
) whenever
∈
(
) \ {
}, is a total dominating function as well. If
is a total weak Roman dominating function and
= ∅, then we say that
is a secure total dominating function. The weight of a function
is defined to be ω(
) = Σ
). The total weak Roman domination number (secure total domination number) of a graph
is the minimum weight among all total weak Roman dominating functions (secure total dominating functions) on
. In this article, we show that these two parameters coincide for lexicographic product graphs. Furthermore, we obtain closed formulae and tight bounds for these parameters in terms of invariants of the factor graphs involved in the product.
A perfect (an n-perfect) pseudo effect algebra can be decomposed into two (n+1 many) non-empty and mutually comparable slices. They generalize perfect MV-algebras studied in 5. We characterize such a ...pseudo effect algebra as an interval in the semidirect product of the po-group Z or 1nZ with a directed po-group G satisfying a stronger type of the Riesz Decomposition Property, RDP1, and the semidirect product is ordered lexicographically. We show that the category of perfect and the category of n-perfect pseudo effect algebras with RDP1 are categorically equivalent to a special category of directed po-groups satisfying RDP1.
PDF
