Decomposition of arbitrary graphs into subgraphs of small size is assuming importance in the literature. There are several studies on the isomorphic decomposition of graphs into paths, cycles, trees, ...stars, sunlet etc. Fork is a tree obtained by subdividing any edge of a star of size three exactly once. In this paper, we investigate the necessary and sufficient for the fork-decomposition of Strong product of graphs.
Let G be a graph and X⊆V(G). Then X is a mutual-visibility set if each pair of vertices from X is connected by a geodesic with no internal vertex in X. The mutual-visibility number μ(G) of G is the ...cardinality of a largest mutual-visibility set. In this paper, the mutual-visibility number of strong product graphs is investigated. As a tool for this, total mutual-visibility sets are introduced. Along the way, basic properties of such sets are presented. The (total) mutual-visibility number of strong products is bounded from below in two ways, and determined exactly for strong grids of arbitrary dimension. Strong prisms are studied separately and a couple of tight bounds for their mutual-visibility number are given.
Given a non-negative integer g, the g-extraconnectivity in a connected graph G is defined as the minimum number of vertices that, when removed, results in G becoming disconnected and each remaining ...component containing more than g vertices. As an extension of the connectivity, the g-extraconnectivity provides a better measurement for the fault tolerance of an interconnection network. The strong product G1⊠G2 of graphs G1 and G2 is the graph with vertex set V(G1)×V(G2), where two distinct vertices (a1,b1) and (a2,b2) are adjacent if and only if a1=a2 and b1b2∈E(G2), or b1=b2 and a1a2∈E(G1), or a1a2∈E(G1) and b1b2∈E(G2). In this paper, we focus on networks modeled by the strongproductG1⊠G2. We determine the g(≤3)-extraconnectivity of G1⊠G2, where G1 and G2 are regular and maximally connected graphs with girth at least g+4. Additionally, we give the g(≤3)-extra conditional diagnosability of G1⊠G2 under PMC model.
•Determined the g (≤3)-extra connectivity of the strong product of regular and maximally connected graphs.•Gave the g(≤3)-extra conditional diagnosability of a class of strong product graphs under PMC model.•Provided two reliability-measurements for the interconnection networks modeled by a class of strong product graphs.
Foucaud, Krishna and Ramasubramony Sulochana recently introduced the concept of monitoring edge-geodetic sets in graphs, and a related graph invariant. These are sets of vertices such that the ...removal of any edge changes the distance between some pair of vertices in the set. They studied the minimum possible size of such a set in a given graph, which we call the monitoring edge-geodetic number.
We show that the decision problem for the monitoring edge-geodetic number is NP-complete. We also give best-possible upper and lower bounds for the Cartesian and strong products of two graphs. These bounds establish the exact value in many cases, including many new examples of graphs whose only monitoring edge-geodetic set is the whole vertex set.
The investigation into the domination problem and the associated subset problem of graphs is a focal point in graph theory research, sparking widespread interest and extensive exploration. This paper ...mainly studies the Italian domination of the strong product of two cycles. By constructing recursive Italian dominating functions, a well-defined bound for the Italian domination number in ... is obtained. Furthermore, through mathematical derivation and proof, the precise Italian domination number of ... is determined.
If each minimal dominating set in a graph is a minimum dominating set, then the graph is called well-dominated. Since the seminal paper on well-dominated graphs appeared in 1988, the structure of ...well-dominated graphs from several restricted classes has been studied. In this paper we give a complete characterization of nontrivial direct products that are well-dominated. We prove that if a strong product is well-dominated, then both of its factors are well-dominated. When one of the factors of a strong product is a complete graph, the other factor being well-dominated is also a sufficient condition for the product to be well-dominated. Our main result gives a complete characterization of well-dominated Cartesian products in which at least one of the factors is a complete graph. In addition, we conjecture that this result is actually a complete characterization of the class of nontrivial, well-dominated Cartesian products.
The concepts of graph theory are applied in many areas of computer science including image segmentation, data mining, clustering, image capturing and networking. Fuzzy graph theory is successfully ...used in many problems, to handle the uncertainty that occurs in graph theory. A single valued neutrosophic graph (SVNG) is an instance of a neutrosophic graph and a generalization of the fuzzy graph, intuitionistic fuzzy graph, and interval-valued intuitionistic fuzzy graph. In this paper, the basic operations on SVNGs such as direct product, Cartesian product, semi-strong product, strong product, lexicographic product, union, ring sum and join are defined. Moreover, the degree of a vertex in SVNGs formed by these operations in terms of the degree of vertices in the given SVNGs in some particular cases are determined. Finally, an application of single valued neutrosophic digraph (SVNDG) in traval time is provided.
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
Let G,H be graphs and G⁎H represent a particular graph product of G and H. We define im(G) to be the largest t such that G has a Kt-immersion and ask: given im(G)=t and im(H)=r, how large is im(G⁎H)? ...Best possible lower bounds are provided when ⁎ is the Cartesian or lexicographic product, and a conjecture is offered for each of the direct and strong products, along with some partial results.
The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the ...second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.
