Jaeger \(et \;al\). [ J. Combin. Theory, Ser B, \(56 (1992) 165-182]\) conjectured that every 3-edge-connected graph is \(Z_5\)-connected. Let \(G\) be a 3-edge-connected simple graph on \(n\) vertices and \(A\) an abelian group with \(|A| \geq 3\). If a graph \(G^*\) is obtained by repeatedly contracting nontrivial \(A\)-connected subgraphs of \(G\) until no such subgraph is left, we say \(G\) can be \(A\)-reduced to \(G^*\). It is proved in this paper that \(G\) is \(A\)-connected with \(|A| \geq 5\) if one of the following holds: (i) \(n \leq 15\); (ii) \(n = 16\) and \(\Delta \geq 4\); or (iii) \(n = 17\) and \(\Delta \geq 5\). As applications, we also show the following results:
(1) For \(|A| \geq 5\) and \(n \geq 17\), if \(|E(G)| \geq \binom{n-15}{2} + 31\), then \(G\) is \(A\)-connected.
(2) For \(|A| \geq 4\) and \(n \geq 13\), if \(|E(G)| \geq \binom{n-11}{2} + 23\), then either \(G\) is \(A\)-connected or \(G\) can be \(A\)-reduced to the Petersen graph.

Given a partial cube \(G\), the \(\Theta\)-graph of \(G\) has \(\Theta\)-classes of \(G\) as its vertices, and two vertices in it are adjacent if the corresponding \(\Theta\)-classes meet in a vertex of \(G\). We present a counter-example to the question from \([8]\) whether \(\Theta\)-graphs of graphs of acyclic cubical complexes are always dually chordal graphs. On a positive side, we show that in the class of ACC \(p\)-expansion graphs, each \(\Theta\)-graph is both a dually chordal and a chordal graph. In the proof, a fundamental characterization of \(\Theta\)-acyclic hypergraphs is combined with techniques from metric graph theory. Along the way, we also introduce a new, weaker version of simplicial elimination scheme, which yields yet another characterization of chordal graphs.

Let \(X = (V, E)\) be a connected vertex-transitive graph with degree \(k\). Call \(X\) super restricted edge-connected, in short, sup-\(\lambda’\), if \(F\) is a minimum edge set of \(X\) such that \(X – F\) is disconnected and every component of \(X – F\) has at least two vertices, then \(F\) is the set of edges adjacent to a certain edge in \(X\). Wang [Y, Q, Wang, Super restricted edge-connectivity of vertex-transitive graphs, Discrete Mathematics \(289 (2004) 199-205]\) proved that a connected vertex-transitive graph with degree \(k > 2\) and girth \(g > 4\) is sup-\(\lambda’\). In this paper, by studying the \(k\)-superatom of \(X\), we present sufficient and necessary conditions for connected vertex-transitive graphs and Cayley graphs with degree \(k > 2\) to be sup-\(\lambda’\). In particular, sup-\(\lambda’\) connected vertex-transitive graphs with degree \(k > 2\) and girth \(g > 3\) are completely characterized. These results can be seen as an improvement of the one obtained by Wang.

A proper vertex coloring of a graph \(G\) is called a dynamic coloring if for every vertex \(v\) with degree at least 2, the neighbors of \(v\) receive at least two different colors. It was conjectured that if \(G\) is a regular graph, then \(\chi_2(G) – \chi(G) \leq 2\). In this paper, we prove that, apart from the cycles \(C_4\) and \(C_5\) and the complete bipartite graphs \(K_{n,n}\), every strongly regular graph \(G\) satisfies \(\chi_2(G) – \chi(G) \leq 1\).

Let \(\vec{P_l}\) be the directed path on \(r\) vertices and \(\lambda K^*_{m,n}\) be the symmetric complete bipartite multi-digraph with two partite sets having \(m\) and \(n\) vertices. A \(\vec{P_l}\)-factorization of \(\lambda K^*_{m,n}\) is a set of arc-disjoint \(\vec{P_l}\)-factors of \(\lambda K^*_{m,n}\), which is a partition of the set of arcs of \(\lambda K^*_{m,n}\). In this paper, it is shown that a necessary and sufficient condition for the existence of a \(\vec{P}_{2k+l}\)-factorization of \(\lambda K^*_{m,n}\) for any positive integer \(k\).

Let \(G = (V, E)\) be a finite non-empty graph. A vertex-magic total labeling (VMTL) is a bijection \(\lambda\) from \(V \cup E\) to the set of consecutive integers \(\{1, 2, \ldots, |V| + |E|\}\) with the property that for every \(v \in V\), \(\lambda(v) + \sum_{w \in N(v)} \lambda(vw) = h\), for some constant \(h\). Such a labeling is called super if the vertex labels are \(1, 2, \ldots, |V|\).
There are some results known about super VMTLs of \(kG\) only when the graph \(G\) has a super VMTL. In this paper, we focus on the case when \(G\) is the complete graph \(K_n\). It was shown that a super VMTL of \(kK_n\) exists for \(n\) odd and any \(k\), for \(4 < n \equiv 0 \pmod{4}\) and any \(k\), and for \(n = 4\) and \(k\) even. We continue the study and examine the graph \(kK_n\) for \(n \equiv 2 \pmod{4}\). Let \(n = 4l + 2\) for a positive integer \(l\). The graph \(kK_{4l+2}\) does not admit a super VMTL for \(k\) odd. We give a large number of super VMTLs of \(kK_{4l+2}\) for any even \(k\) based on super VMTLs of \(4K_{2l+1}\).

For a given graph \(H\), a graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) is said to be potentially \(H\)-graphic if there exists a realization of \(\pi\) containing \(H\) as a subgraph. Let \(K_m – H\) be the graph obtained from \(K_m\) by removing the edge set \(E(H)\), where \(H\) is a subgraph of \(K_m\). In this paper, we characterize the potentially \(K_6 – C_4\)-graphic sequences. This characterization implies a theorem due to Hu and Lai \([7]\).

Double Fibonacci sequences \((x_{n,k})\) are introduced and they are related to operations with Fibonacci modules. Generalizations and examples are also discussed.

A set \(S \subseteq V\) is a dominating set of a graph \(G = (V, E)\) if each vertex in \(V\) is either in \(S\) or is adjacent to a vertex in \(S\). A vertex is said to dominate itself and all its neighbors. The domination number \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\). In terms of a chess board problem, let \(X_n\) be the graph for chess piece \(X\) on the square of side \(n\). Thus, \(\gamma(X_n)\) is the domination number for chess piece \(X\) on the square of side \(n\). In 1964, Yaglom and Yaglom established that \(\gamma(K_n) = \left\lceil \frac{n+2}{2} \right\rceil^2\). This extends to \(\gamma(K_{m,n}) = \left\lceil \frac{m+2}{3} \right\rceil \left\lceil \frac{n+2}{3} \right\rceil\) for the rectangular board. A set \(S \subseteq V\) is a total dominating set of a graph \(G = (V, E)\) if each vertex in \(V\) is adjacent to a vertex in \(S\). A vertex is said to dominate its neighbors but not itself. The total domination number \(\gamma_t(G)\) is the minimum cardinality of a total dominating set of \(G\). In 1995, Garnick and Nieuwejaar conducted an analysis of the total domination numbers for the king’s graph on the \(m \times n\) board. In this paper, we note an error in one portion of their analysis and provide a correct general upper bound for \(\gamma_t(K_{m,n})\). Furthermore, we state improved upper bounds for \(\gamma_t(K_n)\).

A labeling of a graph is a mapping that carries some set of graph elements into numbers (usually the positive integers). An \((a, d)\)-edge-antimagic total labeling of a graph with \(p\) vertices and \(q\) edges is a one-to-one mapping that takes the vertices and edges onto the integers \(1, 2, \ldots, p + q\), such that the sums of the label on the edges and the labels of their end points form an arithmetic sequence starting from \(a\) and having a common difference \(d\). Such a labeling is called \({super}\) if the smallest possible labels appear on the vertices. In this paper, we study the super \((a, 2)\)-edge-antimagic total labelings of disconnected graphs. We also present some necessary conditions for the existence of \((a, d)\)-edge-antimagic total labelings for \(d\) even.