Narrow Results

A vertex subset $S$ of a graph $G$ is a $k$-path vertex cover if $S$ intersects any $k$-path in $G,$ for some positive integer $k.$ The minimum magnitude of all $k$-path vertex covers is called $k$-path vertex cover number of $G$ (denoted ${\psi }_k(G)$). In this contribution, we gave estimations of ${\psi }_k(C_m\square P_n^2),$${\psi }_k(C_m\square S_{n+1})$ and the exact values of ${\psi }_3(P_m\square C_n),$${\psi }_3(C_m\square S_{n+1})$ and ${\psi }_k(P_m\square S_{n+1})$. We also obtain the ${\psi }_k(G)$ when $G$ is the Cartesian product of complete and complete bipartite graph.

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.

The domination integrity of graph G is defined by $DI(G)=min\{|S|+m(G-S):S \text{is a dominating set of} G\}$ where $m(G-S)$ denotes the order of the largest component in $G-S$. This parameter is a measures of vulnerability of a graph. In this paper, we determine the domination integrity of middle graph of graph $B_n$, graph $E_p^t$ and graph $H_n^2$. We also obtain some results for cartesian product and corona.

Let $G=(V,E)$ be a graph and $k$ be an integer representing $k$ colors. There is a function $f$ from $V$ to the power set of $k$ colors satisfying every vertex $v\in V$ assigned $\varnothing$ under $f$ in its neighborhood has all the colors, then $f$ is called a $k$-rainbow dominating function ($k$RDF) on $G$. The weight of $f$ is the sum of the number of colors on each vertex all over the graph. The $k$-rainbow domination number of $G$ is the minimum weight of $k$RDFs on $G$, denoted by ${\gamma }_{rk}(G)$. The aim of this paper is to investigate the $k$-rainbow ($k=3,4$) domination number of the Cartesian product of paths $P_m\square P_n$ and the Cartesian product of paths and cycles $P_m\square C_n$. For $P_m\square P_n$, we determine the value ${\gamma }_{r3}(P_4\square P_n)=2n+2$ and present ${\gamma }_{r3}(P_m\square P_n)\le \frac{mn}{2}+2$ for $m\ge 5$. For $P_m\square C_n$, we determine the values of ${\gamma }_{r3}(P_m\square C_n)$ for $m=3,4$ or $n=3,4$ and ${\gamma }_{r4}(P_m\square C_n)$ for $m=3$ or $n=3$.

An path that is edge-colored is called proper if no two consecutive edges receive the same color. A general graph that is edge-colored is called properly connected if, for every pair of vertices in the graph, there exists a properly colored path from one to the other. Given two vertices u and v in a properly connected graph G, the proper distance is the length of the shortest properly colored path from u to v. By considering a specific class of colorings that are properly connected for Cartesian products of complete and cyclic graphs, we present results on the proper distance between all pairs of vertices in the graph.

In [2], a new problem called conditional cartesian product problem was introduced. The problem has a trivial time lower bound , where A and B are two groups of N elements and C_A,B is a subset of the cartesian product A×B satisfying some unknown condition C. Ben-Asher proposed an efficient algorithm for the problem and showed that the proposed algorithm can be performed in time [2]. As compared with the trivial time lower bound, the algorithm is not optimal. In this paper, with a better analysis, we show that the worst-case time complexity of Ben-Asher’s algorithm is , which is much better than . Consequently, it can be concluded that for case the rate of growth of |C_A,B| is not smaller than is a tight lower bound and Ben-Asher’s algorithm is indeed optimal.

This paper considers synchronization problems in networks of chaotic systems with time-delayed couplings. First of all, we show that synchronization patterns can be estimated from eigenvectors of the graph Laplacian related to the scaling method for synchronization conditions. Then, we consider synchronization in Cartesian product networks. By combining the proposed estimation method with the properties of the Cartesian product, we can easily detect synchronization patterns emerging in the Cartesian product networks from the eigenvalues of the original networks. Some numerical examples are provided to demonstrate the validity of the proposed estimation method.

Classical topology-based operations such as extrusion (or more generally Minkowski sums) are defined by a cartesian product of combinatorial structures describing the topology of geometric space subdivisions. In this paper, we define the cartesian product operation for four different structures: semi-simplicial sets, generalized maps, oriented maps and chains of maps. We follow a homogeneous framework allowing to define the cartesian product for any simplicial and cellular structures derived from simplicial sets and combinatorial maps. This results from the relationships already established between these structures and those used in computational geometry and geometric modeling. For esch structure we have studied, we additionally provide a time-optimal computation algorithm.

In this paper, we compute the Hausdorff dimension of a graph-directed set when the underlying multigraph is a Cartesian product or a tensor product of several multigraphs. We give explicit formulas in terms of the eigenvalues of the graph and the similarity ratios used with each graph.

Given two metric spaces $E,F$, it is well known that,

A linear k-forest is a forest whose components are paths of length at most k. The linear k-arboricity of a graph G, denoted by ${\text{la}}_k(G)$, is the least number of linear k-forests needed to decompose G. Recently, Zuo, He, and Xue studied the exact values of the linear $(n-1)$-arboricity of Cartesian products of various combinations of complete graphs, cycles, complete multipartite graphs. In this paper, for general k we show that $\max \{{\text{la}}_k(G),{\text{la}}_l(H)\}\le {\text{la}}_{\max \{k,l\}}(G\square H)\le {\text{la}}_k(G)+{\text{la}}_l(H)$ for any two graphs G and H. Denote by $G\circ H,G\times H$ and $G⊠H$ the lexicographic product, direct product and strong product of two graphs G and H, respectively. For any two graphs G and H, we also derive upper and lower bounds of ${\text{la}}_k(G\circ H),{\text{la}}_k(G\times H)$ and ${\text{la}}_k(G⊠H)$ in this paper. The linear k-arboricity of a 2-dimensional grid graph, a r-dimensional mesh, a r-dimensional torus, a r-dimensional generalized hypercube and a hyper Petersen network are also studied.

For a graph G and a vertex subset $S\subseteq V(G)$ of at least two vertices, an S-tree is a subgraph T of G that is a tree with $S\subseteq V(T)$. Two S-trees are said to be edge-disjoint if they have no common edge. Let ${\lambda }_G(S)$ denote the maximum number of edge-disjoint S-trees in G. For an integer K with $2\le k\le n$, the generalized k-edge-connectivity is defined as ${\lambda }_k(G)=\min \{{\lambda }_G(S)| S\subseteq V(G),\left|S\right|=k\}$. An S-tree in an edge-colored graph is rainbow if no two edges of it are assigned the same color. Let $k\ge 2$ and l be integers with $1\le \mathcal{l}\le {\lambda }_k(G)$, the $(k,\mathcal{l})$-rainbow edge-index ${rx}_{k,\mathcal{l}}^{\prime }(G)$ of G is the smallest number of colors needed in an edge-coloring of G such that for every set S of k vertices of G, there exist l edge-disjoint rainbow S-trees.

In this paper, we study the $(3,\mathcal{l})$-rainbow edge-index of Cartesian product graphs and get a sharp upper bound for ${rx}_{3,\mathcal{l}}^{\prime }(G\square H)$ , where G and H are connected graphs with orders at least three, and $G\square H$ denotes the Cartesian product of G and H.

The n-dimensional hypercube Q_n is bipancyclic and contains a 3-regular, 3-connected subgraph on l vertices for every even l from 8 to 2ⁿ except 10. In this paper, we strengthen the previous works to Cartesian product of paths. The bipancyclicity and the existence of 3-regular subgraphs of Cartesian product of paths are studied in this paper.

A graph is said to be total-colored if all the edges and vertices of the graph are colored. A path in a total-colored graph is a total proper path if (i) any two adjacent edges on the path differ in color, (ii) any two internal adjacent vertices on the path differ in color, and (iii) any internal vertex of the path differs in color from its incident edges on the path. A total-colored graph is called total-proper connected if any two vertices of the graph are connected by a total proper path of the graph. For a connected graph $G$, the total proper connection number of $G$, denoted by $tpc(G)$, is defined as the smallest number of colors required to make $G$ total-proper connected. In this paper, we study the total proper connection number for the graph operations. We find that $3$ is the total proper connection number for the join, the lexicographic product and the strong product of nearly all graphs. Besides, we study three kinds of graphs with one factor to be traceable for the Cartesian product as well as the permutation graphs of the star and traceable graphs. The values of the total proper connection number for these graphs are all $3$.

Connectivity is a critical parameter which can measure the reliability of networks. Let $T$ be a vertex set of $G$. If $G-T$ has at least $t$ components, then $T$ is a $t$-component cut of $G$. The $t$-component connectivity ${\kappa }^t(G)$ of $G$ is the vertex number of a smallest $t$-component cut. Cartesian product of graphs is a useful method to construct a large network. We will use Cauchy–Schwarz inequality to determine the component connectivity of Cartesian product of some graphs.

An equitable $(t,k)$-tree-coloring of a graph $G$ is defined as a $t$-coloring of vertices of $G$ such that each component of the subgraph induced by each color class is a tree of maximum degree at most $k$, and the sizes of any two color classes differ by at most one. The strong equitable vertex $k$-arboricity of a graph $G$ refers to the smallest integer $t$ such that $G$ has an equitable $(t^{\prime },k)$-tree-coloring for every $t^{\prime }\ge t$. In this paper, we investigate the Cartesian product with respect to the strong equitable vertex $k$-arboricity, and demonstrate the usefulness of the proposed constructions by applying them to some instances of product networks.

Given a connected graph $G$ and $S\subseteq V(G)$ with $\left|S\right|\ge 2$, an $S$-tree is a such subgraph $T=(V^{\prime },E^{\prime })$ of $G$ that is a tree with $S\subseteq V^{\prime }$. Two $S$-trees $T$ and $T^{\prime }$ are edge-disjoint if $E(T)\cap E(T^{\prime })=\varnothing$. Let ${\lambda }_G(S)$ be the maximum size of a set of edge-disjoint $S$-trees in $G$. The ${\lambda }_k$-connectivity of $G$ is defined as ${\lambda }_k(G)=min\{{\lambda }_G(S):S\subseteq V(G),|S|=k\}$. In this paper, we first show some structural properties of edge-disjoint $S$-trees by Fan Lemma and König-ore Formula. Then, the ${\lambda }_4$-connectivity of the Cartesian product of trees is determined. That is, let $T_{n_1},T_{n_2},\dots ,T_{n_k}$ be trees, then ${\lambda }_4(T_{n_1}\square T_{n_1}\cdots \square T_{n_k})=k$ if $|V(T_{n_i})|\ge 4$ for each $i\in \{1,2,\dots ,k\}$, otherwise ${\lambda }_4(T_{n_1}\square T_{n_2}\square \cdots \square T_{n_k})=k-1$. As corollaries, ${\lambda }_4$-connectivity for some graph classes such as hypercubes and meshes can be obtained directly.

The line graph is a very popular research object in graph theory, in complex networks and also in social networks recently. Let $L(K_{m,n})$ be the line graph of the complete bipartite graph $K_{m,n}$ and $P_{k+1}$ be a path of length $k$. In this paper, we give necessary and sufficient conditions for the existence of $P_4$-decompositions of $L(K_{m,n})$.

In this paper, we consider the cancellation problem for the cartesian product of $L$-algebras. Firstly, we show that $L$-algebras with prime element $0$ and $L$-algebras satisfying the condition ($C$) are cancellable. Furthermore, we also prove that the wedge-sum of cancellable $L$-algebras is cancellable and each $L$-algebra can be embedded into a cancellable $L$-algebra. Finally, we give a class of $L$-algebras satisfying the cancellation law which is different from the above $L$-algebras.

Let G be a simple connected graph. A connected dominating set S ⊂ V(G) is called a doubly connected dominating set of G if the subgraph 〈V(G)\S〉 induced by V(G)\S is connected. We show that given any three positive integers a, b, and c with 4 ≤ a ≤ b ≤ c, where b ≤ 2a, there exists a connected graph G such that a = γ_r(G), b = γ_tr(G), and c = γ_cc(G), where γ_r, γ_tr, and γ_cc are, respectively, the restrained domination, total restrained domination, and doubly connected domination parameters. Also, we characterize the doubly connected dominating sets in the join of any graphs and Cartesian product of some graphs. The corresponding doubly connected domination numbers of these graphs are also determined.