Let \(G\) be the circuit graph of any connected matroid. It is proved that the circuit graph of a connected matroid with at least three circuits is \(E_2\)-Hamiltonian.

The Randić index \(R(G)\) of a graph \(G\) is defined by \(R(G) = \sum\limits_{uv} \frac{1}{\sqrt{d(u)d(v)}}\), where \(d(u)\) is the degree of a vertex \(u\) in \(G\) and the summation extends over all edges \(uv\) of \(G\). In this work, we give sharp lower bounds of \(R(G) + g(G)\) and \(R(G) . g(G)\) among \(n\)-vertex connected triangle-free graphs with Randić index \(R\) and girth \(g\).

Hammack and Livesay introduced a new graph operation \(G^{(k)}\) for a graph \(G\), which they called the \(k\)th inner power of \(G\). A graph \(G\) is Hamiltonian if it contains a spanning cycle. In this paper, we show that \(C^{(k)}_n(n \geq 3, k \geq 2)\) is Hamiltonian if and only if \(n\) is odd and \(k = 2\), where \(C_n\) is the cycle with \(n\) vertices.

Let \(a(v)\) and \(g(v)\) denote the least possible area and the least possible number of lattice points in the interior of a convex lattice \(v\)-gon, respectively. Many lower and upper bounds for \(a(v)\) and \(g(v)\) are known for every \(v\). However, the exact values of these two functions are only known for \(v \leq 10\) and \(v \in \{12, 13, 14, 16, 18, 20, 22\}\). The purpose of this paper is to answer the following Open Question 1 from \([13]\): What is the exact value of \(a(11)\)? We answer this question by proving that \(a(11) = 21.5\). On our way to achieve this goal, we also prove that \(g(11) = 17\).

The edge-face total chromatic number of \(3\)-regular Halin graphs was shown to be \(4\) or \(5\) in \([5]\). In this paper, we shall provide a necessary and sufficient condition to characterize \(3\)-regular Halin graphs with edge-face total chromatic number equal to four.

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\).