The g-extra connectivity of graph products Wang, Zhao; Mao, Yaping; Hsieh, Sun-Yuan ...
Journal of computer and system sciences,
November 2024, Letnik:
145
Journal Article
Recenzirano
Connectivity is one of important parameters for the fault tolerant of an interconnection network. In 1996, Fàbrega and Fiol proposed the concept of g-extra connectivity. A subset of vertices S is ...said to be a cutset if G−S is not connected. A cutset S is called an Rg-cutset, where g is a non-negative integer, if every component of G−S has at least g+1 vertices. If G has at least one Rg-cutset, the g-extra connectivity of G, denoted by κg(G), is then defined as the minimum cardinality over all Rg-cutsets of G. In this paper, we first obtain the exact value of g-extra connectivity for the lexicographic product of two general graphs. Next, the upper and lower sharp bounds of g-extra connectivity for the Cartesian product of two general graphs are given. In the end, we apply our results on grid graphs and 2-dimensional generalized hypercubes.
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.
The aim of this paper is to obtain closed formulas for the perfect domination number, the Roman domination number and the perfect Roman domination number of lexicographic product graphs. We show that ...these formulas can be obtained relatively easily for the case of the first two parameters. The picture is quite different when it concerns the perfect Roman domination number. In this case, we obtain general bounds and then we give sufficient and/or necessary conditions for the bounds to be achieved. We also discuss the case of perfect Roman graphs and we characterize the lexicographic product graphs where the perfect Roman domination number equals the Roman domination number.
The generalized k-connectivity κk(G) of a graph G, which was introduced by Chartrand et al. (1984), is a generalization of the concept of vertex connectivity. For this generalization, the generalized ...2-connectivity κ2(G) of a graph G is exactly the connectivity κ(G) of G. In this paper, let G be a connected graph of order n and let H be a 2-connected graph. For Cartesian product, we show that κ3(G□H)≥κ3(G)+1 if κ(G)=κ3(G); κ3(G□H)≥κ3(G)+2 if κ(G) > κ3(G). Moreover, above bounds are sharp. As an example, we show that κ3(Cn1□Cn2□⋯Cnk︷k)=2k−1, where Cni is a cycle. For lexicographic product, we prove that κ3(H∘G)≥max{3δ(G)+1,⌈3n+12⌉} if δ(G)<2n−13, and κ3(H∘G)=2n if δ(G)≥2n−13.
A k-limited packing partition (kLP partition) of a graph G is a partition of V(G) into k-limited packing sets. We consider the kLP partitions with minimum cardinality (with emphasis on k=2). The ...minimum cardinality is called kLP partition number of G and denoted by χ×k(G). This problem is the dual problem of k-tuple domatic partitioning as well as a generalization of the well-studied 2-distance coloring problem in graphs.
We give the exact value of χ×2 for trees and bound it for general graphs. A section of this paper is devoted to the dual of this problem, where we give a solution to an open problem posed in 1998. We also revisit the total limited packing number in this paper and prove that the problem of computing this parameter is NP-hard even for some special families of graphs. We give some inequalities concerning this parameter and discuss the difference between 2TLP number and 2LP number with emphasis on trees.
The resistance distance Ru,v between two vertices u and v of a graph G is defined as the net effective resistance between them in the electric network constructed from G by replacing each edge with a ...unit resistor. The resistance diameter Dr(G) of G is the maximum resistance distance among all pairs of vertices of G. Given two path graphs Pn=a1a2…an and Pm=b1b2…bm, let PnPm be the lexicographic product of Pn and Pm with vertex set {(ai,bj)|i=1,…,n;j=1,…,m}. In J. Appl. Math. Comput. 68 (2022) 1743–1755, Li et al. proved that for n>10, Dr(PnPm)=R(a1,b1),(an,bm)=R(a1,b1),(an,b1)=R(a1,bm),(an,b1)=R(a1,bm),(an,bm). In addition, they found that the result is not true for n=2. For 3≤n≤10 and enough small m, they checked by computer that the result is still true. Based on their observation, they conjectured that the result is true for 3≤n≤10. In this paper, by combinatorial and electrical network approaches, we confirm the conjecture.
For an ordered set $W=\{w_1,w_2,\ldots,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the ordered $k$-vector $r(v|W):=(d(v,w_1),d(v,w_2),\ldots,d(v,w_k))$ is called the (metric) ...representation of $v$ with respect to $W$, where $d(x,y)$ is the distance between the vertices $x$ and $y$. The set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we investigate the metric dimension of the lexicographic product of graphs $G$ and $H$, $GH$, for some known graphs.
Anticenter of Profiles in Products of Graphs Changat, Manoj; Narasimha-Shenoi, Prasanth G.; Thottungal Joseph, Mary Shalet ...
Indian journal of pure and applied mathematics,
09/2023
Journal Article
A function f:V(G)→{0,1,…,k} is called a k-rainbow independent dominating function of G if Vi={x∈V(G):f(x)=i} is independent for 1 ≤ i ≤ k, and for every x ∈ V0 it follows that N(x) ∩ Vi ≠ ∅, for ...every i ∈ k. The k-rainbow independent domination number, γrik(G), of a graph G is the minimum of w(f)=∑i=1k|Vi| over all such functions. In this paper we show that the problem of determining whether a graph has a k-rainbow independent dominating function of a given weight is NP-complete for bipartite graphs and that there exists a linear-time algorithm to compute γrik(G) of trees. In addition, sharp bounds for the k-rainbow independent domination number of the lexicographic product are presented, as well as the exact formula in the case k=2.
