Narrow Results

A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differs by at most 1, and its size is the number of edges that go across the two parts. In this paper, motivated by a well-known result of Edwards about Max-Cut, we study maximum bisections of graphs. Let ${𝒢}=\{P_{\ell }⊠P_k,P_{\ell }⊠C_k,C_{\ell }⊠C_k\}$. For each $G\in {𝒢}$, we show that $G$ admits a bisection of size larger than Edwards’ bound. We also study the maximum bisection of graphs that seem closely related to the strong product of two paths.

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.

Multiprocessor systems are being increasingly adopted and the system reliability is an important perspective for multiprocessor systems. The fault diagnosis has become crucial for achieving high reliability in multiprocessor systems. The precise fault diagnosis diagnoses all processors correctly. In the comparison-based model, it allows a processor to perform diagnosis by contrasting the responses from a pair of neighboring processors through sending the identical assignment. On the basis of comparison-based model, Sengupta and Dahbura (“On self-diagnosable multiprocessor systems: diagnosis by the comparison approach,” IEEE Transaction on Computers, vol. 41, no. 11, pp. 1386–1396, 1992) put forward the MM* model, any processor c diagnoses two processors $c_1$ and $c_2$ if c has direct communication links to them. Sengupta and Dahbura also designed an $O(N^5)$-time precise fault diagnosis algorithm to diagnose faulty processors for general topologies by using the MM* model, where N is the cardinality of processor set in multiprocessor systems. Lately, Ye and Hsieh (“A scalable comparison-based diagnosis algorithm for hypercube-like net-works,” IEEE Transaction on Reliability, vol. 62, no. 4, pp. 789–799, 2013) devised an precise fault diagnosis algorithm to diagnose all faulty processors for hypercube-like networks by using the MM* model with $O(N{({\log }_{2}N)}^2)$ time complexity. On the basis of Hamiltonian cycle properties, we improve the aforementioned results by presenting an O(N)-time precise fault diagnosis algorithm to diagnose all faulty processors for hypercube-like networks by using the MM* model.

The super edge-connectivity${\lambda }^{\prime }(G)$ of a connected graph G is the minimum cardinality of an edge-cut F in G such that every component of G − F contains at least two vertices. Denote by $G⊠H$ the strong product of graphs G and H. For two graphs G and H, Yang proved that $\begin{array}{l}{\lambda }^{\prime }(G⊠H)\ge \min \{2\lambda (H)\lambda (G)+\lambda (H)+2\lambda (G),2\lambda (G)\lambda (H)+\lambda (G)+2\lambda (H)\}\end{array}$. In this paper, we give another proof of this result. In particular, we determine $\begin{array}{l}{\lambda }^{\prime }(G⊠H)=\min \{\delta (G)(|V(H)|+2e(H)),\delta (H)(|V(G)|+2e(G)),\xi (G⊠H\}\end{array}$ if ${\lambda }^{\prime }(G)=\xi (G)$ and ${\lambda }^{\prime }(H)=\xi (H)$, where $\xi (G)$ denotes the minimum edge-degree of a graph G.

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$.

Let γ(D) denote the domination number of a digraph D and let C_m ⊗ C_n denote the strong product of C_m and C_n, the directed cycles of length m, n ≥ 2. In this paper, we determine the exact values Furthermore, we give a lower bound and an upper bound of γ(C_m1 ⊗ C_m2 ⊗ ⋯ ⊗ C_mn) and obtain that when at least n-2 integers of {m₁, m₂, …, m_n} are even (because of the isomorphism, we assume that m₃, m₄, …, m_n are even).

The bondage number $b(G)$ of a graph $G$ is the cardinality of a minimum edge set whose removal from $G$ results in a graph with the domination number greater than that of $G$. It is a parameter to measure the vulnerability of a communication network under link failure. In this paper, we obtain the exact value of the bondage number of the strong product of a complete graph and a path. That is, for any two integers $m\ge 1$ and $n\ge 2$, $b(K_m⊠P_n)=\lceil \frac{m}{2}\rceil$ if $n\equiv 0(\mathrm{\text{mod}}3)$; $m$ if $n\equiv 2$ (mod 3); $\lceil \frac{3m}{2}\rceil$ if $n\equiv 1$ (mod 3). Furthermore, we determine the exact value of the bondage number of the strong product of a complete graph and a special starlike tree.

The concept of monochromatic connectivity was introduced by Caro and Yuster. A path in an edge-colored graph is called a monochromatic path if all the edges on the path are colored the same. An edge-coloring of $G$ is a monochromatic connection coloring ($MC$-coloring, for short) if there is a monochromatic path joining any two vertices in $G$. The monochromatic connection number, denoted by $\mathrm{\text{mc}}(G)$, is defined to be the maximum number of colors used in an $MC$-coloring of a graph $G$. In this paper, we study the monochromatic connection number on the lexicographical, strong, Cartesian and direct products and present several upper and lower bounds for these products of graphs.

A set S of vertices in a connected graph $G=(V,E)$ is called a geodeticset if every vertex not in $S$ lies on a shortest path between two vertices from $S$. A set $D$ of vertices in $G$ is called a dominating set of $G$ if every vertex not in $D$ has at least one neighbor in $D$. A set $S$ is called a geodetic global dominating set of $G$ if $S$ is both geodetic and global dominating set of $G$. The geodetic global domination number is the minimum cardinality of a geodetic global dominating set in $G$. In this paper, we determine the geodetic global domination number of the corona and strong products of two graphs.

The Weighted Padmakar–Ivan (PI) index of a connected, simple graph $G$ is given by ${\mathrm{\text{PI}}}_w(G)={\sum }_{e=(u,v)\in E(G)}((d_G(u)+d_G(v))(|V(G)|-N_G(e)))$, where $N_G(e)$ denotes the number of equidistant vertices of the edge $e$. In this paper, weighted PI index of tensor product and strong product of some graphs are obtained.

Total coloring is a function that assigns colors to the vertices and edges of the graph such that the adjacent and the incident elements receive different colors. The minimum number of colors required for a proper total coloring of a graph $G$ is called the total chromatic number of $G$ and is denoted by ${\chi }^{″}(G)$. Behzad–Vizing conjecture (Total Coloring Conjecture) states that for any graph $G$, ${\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ is the maximum degree of $G$. In this paper, we verify the Behzad–Vizing conjecture for some product graphs.