We construct explicitly the automorphism group of the folded hypercube \(FQ_n\) of dimension \(n > 3\), as a semidirect product of \(N\) by \(M\), where \(N\) is isomorphic to the Abelian group \(\mathbb{Z}_2^{n}\), and \(M\) is isomorphic to \(\mathrm{Sym}(n+1)\), the symmetric group of degree \(n+1\). Then, we will show that the folded hypercube \(FQ_n\) is a symmetric graph.

The Merrifield-Simmons index \(\sigma(G)\) of a graph \(G\) is defined as the number of subsets of the vertex set, in which any two vertices are non-adjacent, i.e., the number of independent vertex sets of \(G\). A tree is called an \(r\)-leaf tree if it contains \(r\) vertices with degree one. In this paper, we obtain the smallest Merrifield-Simmons index among all trees with \(n\) vertices and exactly six leaves, and characterize the corresponding extremal graph.

A family \(\mathcal{G}\) of connected graphs is a family with constant metric dimension if \(\dim(G)\) is finite and does not depend upon the choice of \(G\) in \(\mathcal{G}\). The metric dimension of some classes of plane graphs has been determined in \([2], [3],[ 4], [9], [10], [14], [22]\). In this paper, we extend this study by considering some classes of plane graphs which are rotationally-symmetric. It is natural to ask for the characterization of classes of rotationally-symmetric plane graphs with constant metric dimension.

is almost locally connected if \(B(G)\) is an independent set and for any \(x \in B(G)\), there is a vertex \(y\) in \(V(G) \setminus \{x\}\) such that \(N(x) \cup \{y\}\) induces a connected subgraph of \(G\), where \(B(G)\) denotes the set of vertices of \(G\) that are not locally connected. In this paper, we prove that an almost locally connected claw-free graph on at least \(4\) vertices is Hamilton-connected if and only if it is \(3\)-connected. This generalizes a result by Asratian that a locally connected claw-free graph on at least \(4\) vertices is Hamilton-connected if and only if it is \(3\)-connected [Journal of Graph Theory \(23 (1996) 191-201\)].

We give new expressions for Stirling numbers, and some partial sums of powers and products.

A star coloring of an undirected graph \(G\) is a proper vertex coloring of \(G\) such that any path on four vertices in \(G\) is not bicolored. The star chromatic number \(\chi_s(G)\) of an undirected graph \(G\) is the smallest integer \(k\) for which \(G\) admits a star coloring with \(k\) colors. In this paper, the star chromatic numbers for some infinite subgraphs of Cartesian products of paths and cycles are established. In particular, we show that \(\chi_s(P_i \Box C_j) = 5\) for \(i, j \geq 4\) and \(\chi_s(C_i \Box C_j) = 5\) for \(i, j \geq 30\). We also show that \(\chi_s(P_i \Box P_j \Box P_k) = 6\) for \(i, j, k \geq 4\), \(\chi_s(C_{3} \Box C_{3} \Box C_k) = 7\) for \(k \geq 3\), and \(\chi_s(C_{4i} \Box C_{4j} \Box P_{4k} \Box C_{4l}) \leq 9\) for \(i, j, k, l \geq 1\). Furthermore, we give the star chromatic numbers of \(d\)-dimensional hypercubes for \(d \leq 6\).

Mixed connectivity is a generalization of vertex and edge connectivity. A graph is \((p,0)\)-connected, \(p \geq 0\), if the graph remains connected after removal of any \(p – 1\) vertices. A graph is \((p,q)\)-connected, \(p \geq 0\), \(q \geq 0\), if it remains connected after removal of any \(p\) vertices and any \(q – 1\) edges. Cartesian graph bundles are graphs that generalize both covering graphs and Cartesian graph products. It is shown that if graph \(F\) is \((p_F, q_F)\)-connected and graph \(B\) is \((p_B, q_B)\)-connected, then Cartesian graph bundle \(G\) with fibre \(F\) over the base graph \(B\) is \((p_F + p_B, q_F + q_B)\)-connected. Furthermore, if \(q_F + p_B \geq 0\), then \(G\) is also \((p_F + p_B + 1, q_F + p_B – 1)\)-connected. Finally, let graphs \(G_i\), \(i = 1, \ldots, n\), be \((p_i, q_i)\)-connected and let \(k\) be the number of graphs with \(q_i > 0\). The Cartesian graph product \(G = G_1 \Box G_2 \Box \ldots \Box G_n\) is \((\sum p_i, \sum q_i)\)-connected, and, for \(k \geq 1\), it is also \((\sum p_i + k – 1, \sum q_i – k + 1)\)-connected.

Let \(\gamma_t(D)\) denote the total domination number of a digraph \(D\), and let \(C_m \Box C_n\) denote the Cartesian product graph of \(C_m\) and \(C_n\), where \(C_m\) denotes the directed cycle of length \(m\), \(m \leq n\). In [On domination number of Cartesian product of directed cycles, Information Processing Letters 110 (2010) 171-173], Liu et al. determined the domination number of \(C_2 \Box C_n\), \(C_3 \Box C_n\), and \(C_4 \Box C_n\). In this paper, we determine the exact values of \(\gamma_t(C_m \Box C_n)\) when at least one of \(m\) and \(n\) is even, or \(n\) is odd and \(m = 1, 3, 5,\) or \(7\).

In this paper, a new type of labeled graphs, called modular multiplicative graphs, is introduced and studied. Specifically, we show that every graph is a subgraph of a modular multiplicative graph. Later, we introduce \(k\)-modular multiplicative graphs and prove that certain families of paths and cycles admit such a label. We conclude with several open problems and areas of future possible research, including a note on harmonious graph labels.

Let \(X = (V,E)\) be a digraph. \(X\) is maximally connected if \(\kappa(X) = \delta(X)\). \(X\) is maximally arc-connected if \(\lambda(X) = \delta(X)\). And \(X\) is super arc-connected if every minimum arc-cut of \(X\) is either the set of inarcs of some vertex or the set of outarcs of some vertex. In this paper, we prove that the strongly connected Bi-Cayley digraphs are maximally connected and maximally arc-connected, and most strongly connected Bi-Cayley digraphs are super arc-connected.