Search

In this paper, the newly directed fuzzy graphs are generated using the operations such as union, join, composition and cartesian product of two directed fuzzy graphs, accompanied by their illustrative analysis. The degree of vertices in the newly generated directed fuzzy graphs is defined, and properties based on vertex degree are established. Additionally, the degrees of corresponding vertices in the composition and cartesian product of two directed fuzzy graphs are compared. The orientation of defined operations on fuzzy graphs is compared with the corresponding operations on directed fuzzy graphs and analyzed through illustrative examples. [ABSTRACT FROM AUTHOR]

In graph theory, graph labeling is an essential area of study because labeled graphs offer useful mathematical models for coding theory, cryptography, astronomy, radar, database administration and communication networks. Consider a bijection for a graph G of order n, f : V (G) → {1, 2, ..., n}. The weight of a vertex z of G, expressed as w(z), is defined as the sum of labels assigned to all vertices adjacent to vertex z in G. If the weights are distinct for every unique pair of vertices y, z in V (G), then the labeling f is referred to as distance antimagic. A distance antimagic graph is any graph G that accepts such a labeling. Distance antimagic labeling on various basic graph products are discussed in this paper. We explore results on (a, d)-distance antimagic labeling for the lexicographic product G * H and distance antimagic labeling for the cartesian product G * H, tensor product G x H and strong product G x H in this work, where the graphs G and H are cycle related graphs, paths or complete graphs. Also, computer-aided algorithms are designed to verify that vertex weights are distinct. [ABSTRACT FROM AUTHOR]

In this article, we determine the rainbow mean index of cartesian product G□Pn, where G is a regular graph; Pm□Pn; Wn□K2; total graph of paths; chain of cycles and complete graphs; triangular tree and join graphs tCs∨K1. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V (G) and edge set E(G). Denote by dG(u) the degree of a vertex u ∈ V (G). The Sombor index of G is defined as SO(G) = Σuv∈E(G) √d²u + d²v , whereas, the inverse sum indeg (ISI) index is defined as ISI(G) = Σuv∈E(G) dudv/du+dv . In this paper, we compute the bounds in terms of maximum degree, minimum degree, order and size of the original graphs G and H for Sombor and ISI indices of several graph operations like corona product, cartesian product, strong product, composition and join of graphs. [ABSTRACT FROM AUTHOR]

We study logical reduction (factorization) of relations into relations of lower arity by Boolean or relative products that come from applying conjunctions and existential quantifiers to predicates, i.e. by primitive positive formulas of predicate calculus. Our algebraic framework unifies natural joins and data dependencies of database theory and relational algebra of clone theory with the bond algebra of C.S. Peirce. We also offer new constructions of reductions, systematically study irreducible relations and reductions to them and introduce a new characteristic of relations, ternarity, that measures their 'complexity of relating' and allows to refine reduction results. In particular, we refine Peirce's controversial reduction thesis, and show that reducibility behaviour is dramatically different on finite and infinite domains. [ABSTRACT FROM AUTHOR]

In this paper, we prove Wt □ G and Wt ⊠ G are not distance magic if graph G contains two vertices with the same neighborhood. And we also prove Wt ×C4 (t ≥ 5), W3□Pn and W4 × Pn (n ≥ 3) are not distance magic graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1- product of matrices S 1 ∈ R m 1 × n 1 , S 2 ∈ R m 2 × n 2 is a matrix in R (m 1 + m 2) × (n 1 n 2) whose columns are the concatenation of each column of S 1 with each column of S 2. The k - product generalizes the 1-product, by taking as input two matrices S 1 , S 2 together with k − 1 special rows of each of those matrices, and outputting a certain composition of S 1 , S 2 . Our first result is a polynomial time algorithm for the following problem: given a matrix S , is S a k -product of some matrices, up to permutation of rows and columns? Our algorithm is based on minimizing a symmetric submodular function that expresses mutual information from information theory. Our study is motivated by a close link between the 1-product of matrices and the Cartesian product of polytopes, and more generally between the k -product of matrices and the glued product of polytopes. These connections rely on the concept of a slack matrix, which gives an algebraic representation of classes of affinely equivalent polytopes. The slack matrix recognition problem is the problem of determining whether a given matrix is a slack matrix. This is an intriguing problem whose complexity is unknown. Our algorithm reduces the problem to instances which cannot be expressed as k -products of smaller matrices. In the second part of the paper, we give a combinatorial interpretation of k -products for two well-known classes of polytopes: 2-level matroid base polytopes and stable set polytopes of perfect graphs. We also show that the slack matrix recognition problem is polynomial-time solvable for such polytopes. Those two classes are special cases of 2-level polytopes, for which we conjecture that the slack matrix recognition problem is polynomial-time solvable. [ABSTRACT FROM AUTHOR]

Chung et al. constructed an induced subgraph of the hypercube Qn ${Q}^{n}$ with α(Qn)+1 $\alpha ({Q}^{n})+1$ vertices and with maximum degree smaller than ⌈n⌉ $\lceil \sqrt{n}\rceil $. Subsequently, Huang proved the Sensitivity Conjecture by demonstrating that the maximum degree of such an induced subgraph of hypercube Qn ${Q}^{n}$ is at least ⌈n⌉ $\lceil \sqrt{n}\rceil $, and posed the question: Given a graph G $G$, let f(G) $f(G)$ be the minimum of the maximum degree of an induced subgraph of G $G$ on α(G)+1 $\alpha (G)+1$ vertices, what can we say about f(G) $f(G)$? In this paper, we investigate this question for Cartesian product of paths Pm ${P}_{m}$, denoted by Pmk ${P}_{m}^{k}$. We determine the exact values of f(Pmk) $f({P}_{m}^{k})$ when m=2n+1 $m=2n+1$ by showing that f(P2n+1k)=1 $f({P}_{2n+1}^{k})=1$ for n≥2 $n\ge 2$ and f(P3k)=2 $f({P}_{3}^{k})=2$, and give a nontrivial lower bound of f(Pmk) $f({P}_{m}^{k})$ when m=2n $m=2n$ by showing that f(P2nk)≥⌈2cosπn2n+1k⌉ $f({P}_{2n}^{k})\ge \lceil 2\cos \frac{\pi n}{2n+1}\sqrt{k}\rceil $. In particular, when n=1 $n=1$, we have f(Qk)=f(P2k)≥k $f({Q}^{k})=f({P}_{2}^{k})\ge \sqrt{k}$, which is Huang's result. The lower bounds of f(P3k) $f({P}_{3}^{k})$ and f(P2nk) $f({P}_{2n}^{k})$ are given by using the spectral method provided by Huang. [ABSTRACT FROM AUTHOR]

Throughout this work, the vertex decomposability and shellability of graphs formed from other graphs by various operations are investigated. Also among the other things, by using some graph operations, new classes of Cohen–Macaulay graphs from previous ones are presented. [ABSTRACT FROM AUTHOR]

Counting perfect matchings is an interesting and challenging combinatorial task. It has important applications in statistical physics and chemistry. As the general problem is #P-complete, it is usually tackled by randomized heuristics and approximation schemes. Let GG and HH be two graphs. Denote by G×HG\times H the Cartesian product of graphs GG and HH. The number of perfect matchings of some types of Cartesian product G×HG\times H is investigated by the Pfaffian method, where G≅P2G\cong {P}_{2}, P3{P}_{3}, P4{P}_{4} or C4{C}_{4}, and H≅TH\cong T or HH is a non-bipartite graph with a unique cycle. In this article, we construct a Pfaffian orientation of the graph G×P2G\times {P}_{2}, where GG is a non-bipartite graph with kk odd cycles. We obtain the counting formula on the number of perfect matchings of G×P2G\times {P}_{2}.

A path in an edge-coloured graph is called properly coloured path , or more simply, proper path if every two consecutive edges receive distinct colours. An edge-coloured graph G is called properly k -connected if every two vertices are connected by at least k internally pairwise vertex-disjoint proper paths. The proper k -connection number of a k -connected graph G , denoted by p c k (G) , is the smallest number of colours that are needed in order to make G properly k -connected. In this paper, we study the proper 2-connection number p c 2 (G) of graphs. We prove a new upper bound for p c 2 (G) and determine several classes of graphs satisfying p c 2 (G) = 2. Among these are all graphs satisfying the Chvátal and Erdős condition (α (G) ≤ κ (G)) with two exceptions). We also study the relationship between the proper 2-connection number p c 2 (G) and the proper connection number p c (G) of the Cartesian product of two connected graphs. [ABSTRACT FROM AUTHOR]

Component orthogonal arrays (COAs), as subsets of all possible permutations on experimental factors, are suitable for designing order-of-addition experiments due to their pairwise balance property between any two positions of the orders. When the levels of components can be changed, the standard statistical design method has been to use the Cartesian product design, which often results in a large number of experimental runs. In this article, we consider combining COAs and 2m−p factional factorial designs by using a Subcartesian product. A systematic method is given for design construction. In the construction method, both the COA and 2m−p design are sliced properly, and then the two designs are combined by the Subcartesian product. We show that the number of runs obtained by the Subcartesian product method is usually much smaller than that obtained by the Cartesian product method. In addition, the constructed design satisfies the pairwise balance property and has the same D-efficiency as the full m ! × 2 m design under the main-effect model. Examples are given to illustrate the proposed method. [ABSTRACT FROM AUTHOR]

For a positive integer k , a proper k -coloring of a graph G is a mapping f : V (G) → { 1 , 2 , ... , k } such that f (u) ≠ f (v) for each edge u v of G. The smallest integer k for which there is a proper k -coloring of G is called the chromatic number of G , denoted by χ (G). A locally identifying coloring (for short, lid-coloring) of a graph G is a proper k -coloring of G such that every pair of adjacent vertices with distinct closed neighborhoods has distinct set of colors in their closed neighborhoods. The smallest integer k such that G has a lid-coloring with k colors is called locally identifying chromatic number (for short, lid-chromatic number) of G , denoted by χ l i d (G). This paper studies the lid-coloring of the Cartesian product and tensor product of two graphs. We prove that if G and H are two connected graphs having at least two vertices, then (a) χ l i d (G □ H) ≤ χ (G) χ (H) − 1 and (b) χ l i d (G × H) ≤ χ (G) χ (H). Here G □ H and G × H denote the Cartesian and tensor products of G and H , respectively. We determine the lid-chromatic numbers of C m □ P n , C m □ C n , P m × P n , C m × P n and C m × C n , where C m and P n denote a cycle and a path on m and n vertices, respectively. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is said to be word-representable if a word w can be formed using the letters of the alphabet V such that for every pair of vertices x and y , x ≠ y , x y ∈ E if and only if x and y alternate in w. Gaetz and Ji have recently introduced the notion of minimum length word-representants for word-representable graphs. They have also determined the minimum possible length of the word-representants for certain classes of graphs, such as trees and cycles. It is known that Cartesian and rooted products preserve word-representability. Moreover, using occurrence-based functions, Broere constructed a uniform word representing the Cartesian product of G and K n. In this paper, we study the minimum length of word-representants for Cartesian and rooted products using morphism and occurrence-based functions, respectively. Also, we solve an open problem posed by Broere in his master thesis. This problem asks to construct a word for the Cartesian product of two arbitrary word-representable graphs. [ABSTRACT FROM AUTHOR]

Graph operation is an effective way to synthetize several kinds of big graphs from small factor graphs. Subdivided graph ( S (Γ) ) is a graph obtained by adding a vertex to each edge of graph Γ , while vertex-semi total graph ( R (Γ) ) is the graph obtained by adding a new vertex corresponding to each edge of graph Γ and joining the new vertex to the end vertices of the corresponding edge. Subdivided sum graph and vertex-semi total sum graph are two kinds of ψ -sum graphs generated by utilizing Cartesian product operation for ψ (Γ 1) and Γ 2 , denoted by Γ 1 + ψ Γ 2 , where ψ ∈ { S , R } . In this work, we establish the Laplacian spectrum of Γ 1 + S Γ 2 and Γ 1 + R Γ 2 of k-regular graph Γ 1 and any connected graph Γ 2 in terms of Laplacian spectrum of factor graphs. As applications, we determine the Kirchhoff index, global mean-first passage time and number of spanning trees of Γ 1 + S Γ 2 and Γ 1 + R Γ 2 , respectively. [ABSTRACT FROM AUTHOR]

Covering array (CA) on a hypergraph H is a combinatorial object used in interaction testing of a complex system modeled as H. Given a t-uniform hypergraph H and positive integer s, it is an array with a column for each vertex having entries from a finite set of cardinality s, such as Z s , and the property that any set of t columns that correspond to vertices in a hyperedge covers all s t ordered t-tuples from Z s t at least once as a row. Minimizing the number of rows (size) of CA is important in industrial applications. Given a hypergraph H, a CA on H with the minimum size is called optimal. Determining the minimum size of CA on a hypergraph is NP-hard. We focus on constructions that make optimal covering arrays on large hypergraphs from smaller ones and discuss the construction method for optimal CA on the Cartesian product of a Cayley hypergraph with different families of hypergraphs. For a prime power q > 2 , we present a polynomial-time approximation algorithm with approximation ratio ⌈ log q | V | 3 k - 1 ⌉ 2 for constructing covering array CA(n, H, q) on 3-uniform hypergraph H = (V , E) with k > 1 prime factors with respect to the Cartesian product. [ABSTRACT FROM AUTHOR]

For any hereditary graph class F, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F. As a consequence, we show that, if F admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F do too. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020]. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. A set S ⊆ V (G) is convex 2-dominating if S is both convex and 2-dominating. The minimum cardinality among all convex 2-dominating sets in G, denoted by γ2con(G), is called the convex 2-domination number of G. In this paper, we initiate the study of convex 2- domination in graphs. We show that any two positive integers a and b with 6 ≤ a ≤ b are, respectively, realizable as the convex domination number and convex 2-domination number of some connected graph. Furthermore, we characterize the convex 2-dominating sets in the join, corona, lexicographic product, and Cartesian product of two graphs and determine the corresponding convex 2-domination number of each of these graphs. [ABSTRACT FROM AUTHOR]

Let D = (V, A) be a digraph of order n, S a subset of V of size k and 2 ≤ k ≤ n. A strong subgraph H of D is called an S-strong subgraph if S ⊆ V (H). A pair of S-strong subgraphs D1 and D2 are said to be arcdisjoint if A(D1) ∩ A(D2) = ∅. Let λS(D) be the maximum number of pairwise arc-disjoint S-strong subgraphs in D. The strong subgraph k-arcconnectivity is defined as λk(D) = min{λS(D) | S ⊆ V (D), |S| = k}. The parameter λk(D) can be seen as a generalization of classical edgeconnectivity of undirected graphs. In this paper, we first obtain a formula for the arc-connectivity of Cartesian product λ(G✷H) of two digraphs G and H generalizing a formula for edge-connectivity of Cartesian product of two undirected graphs obtained by Xu and Yang (2006). Using this formula, we get a new formula for the arc-connectivity of Cartesion product of k ≥ 2 copies of a strong digraph G: λ(Gk) = k · min {δ+ (G), δ- (G)}. Then we study the strong nnectivity of Cartesian product λ2(G✷H) and prove that min {λ(G)|H|, λ(H)|G|, δ+(G) + δ+(H), ***δ-(G) + δ-(H)} ≥ λ2(G✷H) ≥ λ2(G) + λ2(H) - 1. The upper bound for λ2(G✷H) is sharp and is a simple corollary of the formula for λ(G✷H). The lower bound for λ2(G✷H) is either sharp or almost sharp i.e., differs by 1 from the sharp bound. We improve the lower bound under an additional condition and prove its sharpness by showing that λ2(G✷H) ≥ λ2(G) + λ2(H), where G and H are two strong digraphs such that δ+ (H) > λ2(H). We also obtain exact values for λ2(G✷H), where G and H are digraphs from some digraph families. [ABSTRACT FROM AUTHOR]

Carleman’s formulas solve the problem of recovery of a function from such a class of its values on the set of uniqueness M ⊂ ∂D for this class that does not contain the Shilov boundary ∂D. In this paper, by using the matrix upper half-plane and the biholomorphic equivalence of the matrix unit disc, the Carleman formula for the Cartesian product of matrix upper half-planes is proved. [ABSTRACT FROM AUTHOR]

For a poset P = (X , ≤ P) , the strict-double-bound graph (sDB (P)) of P = (X , ≤ P) is the graph with the vertex set X such that u v ∈ E (sDB (P)) if and only if u ≠ v and there exist x ∈ X and y ∈ X distinct from u and v such that x ≤ P u ≤ P y and x ≤ P v ≤ P y. For a connected graph G , the strict-double-bound number ζ (G) is defined as min { l : there exists a poset P such that sDB(P) ≅ G ∪ N l } , where N l is the graph with l vertices and no edges. In this paper we deal with the strict-double-bound numbers of Cartesian products of graphs. We show that ζ (P n × P m) ≤ 2 n + 2 m − 4 for n , m ≥ 2 , ζ (C 4 n × C 4 m) ≤ 8 n m + 4 for n , m ≥ 1 , and ζ (C n × C m) ≤ 4 n + 4 m − 4 for n , m ≥ 3. [ABSTRACT FROM AUTHOR]

The operations in spectral fuzzy graphs such as Cartesian product, strong product, bipartite double, Kronecker product and Lexicographic product (composition) are analysed to elucidate the impact of eigenvalue spectra. Also, the properties are derived which delves the effect on spectral fuzzy graphs. [ABSTRACT FROM AUTHOR]

AbstractIn this paper, we discuss the A-vertex magicness of some products of graphs, where A is a non-trivial additive Abelian group with identity 0. We characterize A-vertex magicness of the Cartesian product of Pn and Pm, where A has at least three elements, and we also discuss the A -vertex magicness of co-normal and tensor product of two graphs. Finally, we give a new method to construct an infinite number of A-vertex magic graphs from existing ones using the join operation. As a consequence we obtain an earlier result in [Balamoorthy et al. in AKCE Int. J. Graphs Comb. (2022) 19 (3), 268–275]

Zero forcing is a combinatorial game played on a graph with the ultimate goal of changing the colour of all the vertices at minimal cost. Originally this game was conceived as a one player game, but later a two-player version was devised in-conjunction with studies on the inertia of a graph, and has become known as the q -analogue of zero forcing. In this paper, we study and compute the q -analogue zero forcing number for various families of graphs. We begin with by considering a concept of contraction associated with trees. We then significantly generalize an equation between this q -analogue of zero forcing and a corresponding nullity parameter for all threshold graphs. We close by studying the q -analogue of zero forcing for certain Kneser graphs, and a variety of cartesian products of structured graphs. [ABSTRACT FROM AUTHOR]

The metric theory of limsup sets is the main topic in metric Diophantine approximation. A very simple observation by Erdös shows the dimension of the Cartesian product of two sets of Liouville numbers is 1. To disclose the mystery hidden there, we consider and present a general principle for the Hausdorff dimension of the Cartesian product of limsup sets. As an application of our general principle, it is found that \begin{equation*} \dim _{\mathcal H}W(\psi)\times \cdots \times W(\psi)=d-1+\dim _{\mathcal H}W(\psi) \end{equation*} where W(\psi) is the set of \psi-well approximable points in \mathbb {R} and \psi : \mathbb {N}\to \mathbb {R}^+ is a positive non-increasing function. Even this concrete case was never observed before. Our result can also be compared with Marstrand's famous inequality on the dimension of the Cartesian product of general sets. [ABSTRACT FROM AUTHOR]

An injective k -edge-coloring of a graph G = (V , E) is an assignment ω : E → { 1 , 2 , ... , k } of colors to the edges of G such that any two edges e and f receive distinct colors if there exists an edge g = x y different from e and f such that e is incident on x and f is incident on y. The least number of colors required by any injective edge coloring of G is called the injective chromatic index of G and is denoted by χ i ′ (G). In this paper, we give tight upper bounds of the injective chromatic index of various standard graph products and operations, including the Cartesian product, lexicographic product, corona product, edge corona product, join, subdivision and Mycielskian of a graph. [ABSTRACT FROM AUTHOR]

The problem of injective coloring in graphs can be revisited through two different approaches: coloring the two-step graphs and vertex partitioning of graphs into open packing sets, each of which is equivalent to the injective coloring problem itself. Taking these facts into account, we observe that the injective coloring lies between graph coloring and domination theory. We make use of these three points of view in this paper so as to investigate the injective coloring of some well-known graph products. We bound the injective chromatic number of direct and lexicographic product graphs from below and above. In particular, we completely determine this parameter for the direct product of two cycles. We also give a closed formula for the corona product of two graphs. [ABSTRACT FROM AUTHOR]

For a positive integer k, a subset S of vertices of a graph G is k-independent if each vertex in S has at most k − 1 neighbors in S. We consider k-independent sets in two graph products: Cartesian and complementary prism. We show that the problem of determining k-independence remains NP-complete even for Cartesian products and complementary prisms. Furthermore, we present results on k-independence in the Cartesian product of two paths, known as grid graphs. [ABSTRACT FROM AUTHOR]

For a given graph G, the mutual-visibility problem asks for the largest set of vertices M ⊆ V (G) with the property that for any pair of vertices u , v ∈ M there exists a shortest u, v-path of G that does not pass through any other vertex in M. The mutual-visibility problem for Cartesian products of a cycle and a path, as well as for Cartesian products of two cycles, is considered. Optimal solutions are provided for the majority of Cartesian products of a cycle and a path, while for the other family of graphs, the problem is completely solved. [ABSTRACT FROM AUTHOR]

A vertex coloring is called distinguishing if the identity is the only automorphism that can preserve it. The distinguishing threshold θ(G) of a graph G is the minimum number of colors k required that any arbitrary k-coloring of G is distinguishing. In this paper, we calculate the distinguishing threshold of a Cartesian product graph. Moreover, we calculate the number of non-equivalent distinguishing colorings of grids. [ABSTRACT FROM AUTHOR]

All the graphs considered in this paper are simple and undirected. Let G = (V (G),E(G)) be a simple undirected graph. A function f : V (G) →{0, 1, 2} is called root cube mean cordial labeling if the induced function f∗ : E(G) →{0, 1, 2} defined by f∗(uv) = ⌊(f(u))3 +(f(v))3 2 ⌋ satisfies the condition |vf(i) − vf(j)|≤ 1 and |ef(i) − ef(j)|≤ 1 for any i,j ∈{0, 1, 2}, where vf(x) and ef(x) denotes the number of vertices and number of edges with label x, respectively, and ⌊x⌋ denotes the greatest integer less than or equals to x. The G is called root cube mean cordial if it admits root cube mean cordial labeling. In this paper, we have discussed root cube mean cordial labeling of some graphs. Also, we have provided some graphs which are not root cube mean cordial. [ABSTRACT FROM AUTHOR]

In this note, first, we describe the (minimal) hereditary saturated subsets of finite acyclic graphs and finite graphs whose cycles have no exits. Then we show that the Cartesian product of an -cycle by an -line has nontrivial hereditary saturated subsets even though the graphs and themselves have only trivial hereditary saturated subsets. Tomforde (Theorem 5.7 in "Uniqueness theorems and ideal structure for Leavitt path algebras," J. Algebra 318 (2007), 270–299) proved that there exists a one-to-one correspondence between the set of graded ideals of the Leavitt path algebra of a graph and the set of hereditary saturated subsets of . This shows that the algebraic structure of the Leavitt path algebra of the Cartesian product is plentiful. We also prove that the invariant basis number property of can be derived from that of . More generally, we also show that the invariant basis number property of can be derived from that of if is a finite graph without sinks. [ABSTRACT FROM AUTHOR]

Let G be a graph and C a finite set of colours. A vertex colouring f: V (G) → C is complete if for any pair of distinct colours c1, c2 ∈ C one can find an edge {v1, v2} ∈ E(G) such that f(vi) = ci, i = 1, 2. The achromatic number of G is defined to be the maximum number achr(G) of colours in a proper complete vertex colouring of G. In the paper achr(K6ʸKq) is determined for any integer q such that either 8 ≤ q ≤ 40 or q ≥ 42 is even. [ABSTRACT FROM AUTHOR]

Let D = (V (D) , A (D)) be a digraph of order n and let r ∈ S ⊆ V (D) with 2 ≤ | S | ≤ n . A directed (S , r) -Steiner path (or an (S , r) -path for short) is a directed path P beginning at r such that S ⊆ V (P) . Arc-disjoint between two (S , r) -paths is characterized by the absence of common arcs. Let λ S , r p (D) be the maximum number of arc-disjoint (S , r) -paths in D. The directed path k-arc-connectivity of D is defined as λ k p (D) = min { λ S , r p (D) ∣ S ⊆ V (D) , S = k , r ∈ S }. In this paper, we shall investigate the directed path 3-arc-connectivity of Cartesian product λ 3 p (G □ H) and prove that if G and H are two digraphs such that δ 0 (G) ≥ 4 , δ 0 (H) ≥ 4 , and κ (G) ≥ 2 , κ (H) ≥ 2 , then λ 3 p (G □ H) ≥ min 2 κ (G) , 2 κ (H) ; moreover, this bound is sharp. We also obtain exact values for λ 3 p (G □ H) for some digraph classes G and H, and most of these digraphs are symmetric. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. A function f : V (G) → {0, 1, 2} is a convex Roman dominating function (or CvRDF) if every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2 and V1 ∪ V2 is convex. The weight of a convex Roman dominating function f, denoted by ωG CvR(f), is given byωG CvR (f) =∑ v∈V(G) f(v). The minimum weight of a CvRDF on G, denoted by γCvR(G), is called the convex Roman domination number of G. In this paper, we specifically study the concept of convex Roman domination in the corona and edge corona of graphs, complementary prism, lexicographic product, and Cartesian product of graphs. [ABSTRACT FROM AUTHOR]

We consider the problem of extending partial edge colorings of iterated cartesian products of even cycles and paths, focusing on the case when the precolored edges satisfy either an Evans-type condition or is a matching. In particular, we prove that if G = C d 2k is the dth power of the cartesian product of the even cycle C2k with itself, and at most 2d−1 edges of G are precolored, then there is a proper 2d-edge coloring of G that agrees with the partial coloring. We show that the same conclusion holds, without restrictions on the number of precolored edges, if any two precolored edges are at distance at least 4 from each other. For odd cycles of length at least 5, we prove that if G = C d 2k+1 is the dth power of the cartesian product of the odd cycle C2k+1 with itself (k ≥ 2), and at most 2d edges of G are precolored, then there is a proper (2d+1)-edge coloring of G that agrees with the partial coloring. Our results generalize previous ones on precoloring extension of hypercubes [Journal of Graph Theory 95 (2020) 410–444]. [ABSTRACT FROM AUTHOR]

For two sets of nonnegative integers A and B, the distance between these two sets, denoted by d(A, B), is defined by d (A , B) = min { | a - b | : a ∈ A , b ∈ B } . For a positive integer n, let S n denote the family { X : X ⊆ N ∪ { 0 } , | X | = n } . Given a graph G and positive integers n, p and q, an n-fold L(p, q)-labeling of G is a function f : V (G) → S n satisfies d (f (u) , f (v)) ≥ p if d G (u , v) = 1 , and d (f (u) , f (v)) ≥ q if d G (u , v) = 2 . An n-fold k-L(p, q)-labeling f of G is an n-fold L(p, q)-labeling of G with the property that max { a : a ∈ ⋃ u ∈ V (G) f (u) } ≤ k . The smallest number k to guarantee that G has an n-fold k-L(p, q)-labeling is called the n -fold L(p, q)-labeling number of G and is denoted by λ p , q n (G) . When p = 2 , q = 1 , we use λ n (G) to replace λ 2 , 1 n (G) for simplicity. We study the n-fold L(2, 1) -labeling numbers of Cartesian product of paths and cycles in this paper. We give a necessary and sufficient condition for λ n (C m □ P 2) equals 4 n + 1. Based on this, we determine the exact value of λ 2 (C m □ P 2) (except for m = 5 , 6 and 9) and λ 3 (C m □ P 2) (except for m = 5 , 6 , 9 , 10 , 13 and 17). We also give bounds for λ n (C m □ P k) when n, m satisfy certain conditions, and from this, we obtain the exact value of λ 2 (P m □ P k) (except for the case P 4 □ P 3 ). [ABSTRACT FROM AUTHOR]

Let G be a simple, undirected graph with n vertices and m edges and S k (G) the sum of its k largest Laplacian eigenvalues. Brouwer conjectured that S k (G) ≤ m + ( k + 1 2 ) for any 1 ≤ k ≤ n. We show that if G and H are simple undirected graphs satisfying Brouwer's Conjecture, then the cartesian product G □ H also satisfies Brouwer's Conjecture. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Zhejiang University (Science Edition) is the property of Journal of Zhejiang University (Science Edition) Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Journal of Xinjiang University (Natural Science Edition) is the property of Xinjiang University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Transferring multimedia content without detection has gained traction over time. Employing steganography for hiding secret data, viz. passwords, medical information, and private messages, has become the norm. This work involves hiding confidential information in the images. It aims to increase the payload capacity by adaptively choosing the embedding pixel location, using hamming distance, and increasing the number of bits embedded per pixel using threshold while retaining the image quality. The secret PHI information was embedded into the medical cover image by choosing the pixels, such that the embedding order was random. The randomness in the embedding order was achieved by generating a random sequence using a Combined Logistical Tent map. (CLT map). The random sequence was used as the key to choose all the pixels, but in a random order for embedding. Two different ways can generate the CLT map. One is by generating the Logistical map sequence and Tent map sequence and performing the XOR operation of both sequences. The other way is to generate the CLT map sequence through governing equations. The algorithm is designed to perform embedding for images of various modalities, viz. effectively., Grayscale, RGB and DICOM. The algorithm was tested for over 100 images across databases. The test results were satisfactory. The resultant stego image has an acceptable range of Peak Signal to Noise Ratio (PSNR) values above 40 dB and Structural Similarity Index (SSIM) values above 0.9. The stego images with visually imperceptible secret information are good quality and could effectively mitigate steganalysis. [ABSTRACT FROM AUTHOR]

Let |$H$| be a cartesian product graph of even cycles and paths, where the first multiplier is an even cycle of length at least |$4$| and the second multiplier is a path with at least two nodes or an even cycle. Then |$H$| is an equitable bipartite graph, which takes the torus, the column-torus and the even |$k$| -ary |$n$| -cube as its special cases. For any node |$w$| of |$H$| and any two different nodes |$u$| and |$v$| in the partite set of |$H$| not containing |$w$|⁠ , an algorithm was introduced to construct a hamiltonian path connecting |$u$| and |$v$| in |$H-w$|⁠. [ABSTRACT FROM AUTHOR]

Let S M = { 0 , x , x 2 , ... , x n } be a monogenic semigroup with zero. Here, we consider the power graph ( M) over M with vertex set M ∗ = M \ { 0 } and two distinct vertices x i and x j are adjacent if i divides j or j divides i , where 1 ≤ i , j ≤ n. We compute various graph parameters of ( M) and topological indices based on distance of vertices. Finally, we compute some graph parameters of the cartesian product ( M 1) □ ( M 2) of graphs ( M 1) and ( M 2). [ABSTRACT FROM AUTHOR]

As a hot issue in the field of algebraic graph theory, the quasi-Laplacian energy of a graph is a graph invariant in terms of the quasi-Laplacian spectrum, and is versatile in multidisciplinarity, such as social network analysis, theoretical computer science, mathematical chemistry, and so on. Let Γ be an n-vertex connected graph with quasi-Laplacian eigenvalues μ 1 ⩾ μ 2 ⩾ ⋯ ⩾ μ n ⩾ 0 . The quasi-Laplacian energy of Γ is defined as E Q Γ = ∑ i = 1 n μ i 2 . The ψ -sum graphs are generated by utilizing Cartesian product operation for ψ (Γ 1) and Γ 2 , denoted by Γ 1 + ψ Γ 2 . In this paper, in terms of quasi-Laplacian energy of factor graphs, we characterize the quasi-Laplacian energy of four kinds of ψ -sum graphs. As applications, we determine the quasi-Laplacian energy of several special ψ -sum graphs generated by base graphs, i.e., path, cycle, complete graph and complete bipartite graph, respectively. [ABSTRACT FROM AUTHOR]

With the gradual entry into the era of "Internet of Things", large-scale parallel and distributed systems play a crucial role, which motivates us to explore qualitative and quantitative metric to characterize the fault tolerance and reliability of these systems. A more accurate assessment about the fault tolerance and reliability of large-scale parallel and distributed systems can be achieved by h-extra edge-connectivity. It can dynamically measure the size of the separated component under large-scale faulty links. The use of cartesian product operations to assemble large-scale interconnection networks has received extensive attention due to easy operation and scalability. Given a recursively assembled interconnection network G, the distribution of its values of h-extra edge-connectivity is non-uniform. The h-extra edge-connectivity of G, if any, is well-defined for each positive integer 1 ≤ h ≤ ⌊ | V (G) | / 2 ⌋ . This paper focuses on the concentration phenomenon about h-extra edge-connectivity of the n-th cartesian product of interconnection network K 4 (denoted by λ h (K 4 n) ): as n → ∞ , for about 64.5% of positive integers h ≤ 2 × 4 n - 1 , the h-extra edge-connectivities of the n-th cartesian product of interconnection network K 4 are concentrated on 3n numbers. That is, at least [ 3 n g - 3 g t - g (g - 1) ] 4 t links must be deleted to disconnect network K 4 n , provided that the deletion of these links does not isolate any subnetwork with at most h - 1 processors for about 64.5% of positive integers h ≤ 2 × 4 n - 1 , 0 ≤ t ≤ n - 1 and g ∈ { 1 , 2 , 3 } . It is exactly equal to the minimum cardinality of links, such that whose removal will disconnect the network K 4 n with all its resulting components having at least g × 4 t processors. Our results provide a more precise way to evaluate the reliability of interconnection networks. [ABSTRACT FROM AUTHOR]

Given a graph G = (V,E), a function f : V → {0, 1, 2, 3} having the property that if f(v) = 0, then there exist v1, v2 ϵ N(v) such that f(v1) = 2 = f(v2) or there exists w ϵ N(v) such that f(w) = 3, and if f(v) = 1, then there exists w ϵ N(v) such that f(w) ≥ 2 is called a double Roman dominating function (DRDF). The weight of a DRDF f is the sum f(V ) = ∑vϵV f(v), and the minimum among the weights of DRDFs on G is the double Roman domination number, γdR(G), of G. In this paper, we study the impact of cartesian product on the double Roman domination number. [ABSTRACT FROM AUTHOR]

The crossing number of a graph G , denoted by cr (G) , is defined to be the minimum number of crossings that arise among all its drawings in the plane. This concept has been of interest to many researchers who have studied it for many families of graphs. In this paper, we introduce the crossing number of Cartesian product of sunlet graph S m with path P n . Further, we prove that the crossing number of S m □ P 2 is equal to m , along with giving a conjecture for the general case. In addition, we utilize the vertex's rotation concept in order to prove some necessary conditions for the complete bipartite graph K m , n to be optimal when it is drawn in the plane, by presenting an upper bound for the crossing number of any subgraph in it together with determining the exact number of crossings in case the vertices of subgraph have the same rotation. [ABSTRACT FROM AUTHOR]