A proper vertex coloring of a graph \(G = (V, E)\) is acyclic if \(G\) contains no bicolored cycle. A graph \(G\) is acyclically \(L\)-list colorable if for a given list assignment \(L = \{L(v) : v \in V\}\), there exists a proper acyclic coloring \(\phi\) of \(G\) such that \(\phi(v) \in L(v)\) for all \(v \in V(G)\). If \(G\) is acyclically \(L\)-list colorable for any list assignment with \(|L(v)| = k\) for all \(v \in V\), then \(G\) is acyclically \(k\)-choosable. In this paper, it is proved that every toroidal graph without 4- and 6-cycles is acyclically \(5\)-choosable.

The centro-polyhedral group \(\langle l,m,n\rangle\), for \(l, m, n \in \mathbb{Z}\), is defined by the presentation
\[\langle x, y, z : x^l = y^m = z^n = xyz \rangle.\]
In this paper, we obtain the periods of \(k\)-nacci sequences in centro-polyhedral groups and related groups.

We study two-path convexity in bipartite tournaments. For a bipartite tournament, we obtain both a necessary condition and a sufficient condition on the adjacency matrix for its rank to be two. We then investigate 4-cycles in bipartite tournaments of small rank. We show that every vertex in a bipartite tournament of rank two lies on a four cycle, and bipartite tournaments with a maximum number of 4-cycles do not necessarily have minimum rank.

A set \(S\) of vertices in a graph \(G\) is a clique dominating set of \(G\) if \(S\) contains at least one vertex of every clique \(C\) of \(G\). The clique domination number \(\gamma_q(G)\) and the upper clique domination number \(\gamma_q(G)\) are, respectively, the minimum and maximum cardinalities of a minimal clique dominating set of \(G\). In this paper, we prove that the problem of computing \(\Gamma_q(G)\) is NP-complete even for split graphs and the problem of computing \(\gamma_q(G)\) is NP-complete even for chordal graphs. In addition, for a block graph \(BG\) we show that the clique domination number is bounded above by the vertex independence number (\(\gamma_q(BG) \leq \beta(BG)\)) and give a linear algorithm for computing \(\gamma_q(BG)\).

Katerinis established the following result in [1]. Let \(G\) be a simple graph with \(\delta(G) \geq \lfloor\frac{|V(G)|}{2}+k\), where \(k\) is a non-negative integer. Let \(f : V(G) \to \mathbb{Z}^+\) be a function having the following properties:

(1) \(\frac{1}{2}\left({d_G(v) – (k+1)}{2}\right) \leq f(v) \leq \frac{1}{2}\left({d_G(v) + (k+1)}{2}\right)\) for every \(v \in V(G)\),

(2) \(\sum_{v\in V(G)} f(v) = |E(G)|\).

Then \(G\) has an orientation \(D\) such that \(d^+_D(v) = f(v)\), for every \(v \in V(G)\). In this paper, we focus on the sharpness of the above two inequalities.

A cosimple regular matroid \(M\) does not have disjoint circuits if and only if \(M \in \{M(K_{3,3}), M^*(K_n) \mid n \geq 3\}\). This extends a former result of Erdős and Pósa on graphs without disjoint circuits.

Suppose \(G\) is a finite graph with vertex-set \(V(G)\) and edge-set \(E(G)\). An \((a, d)\)-edge-antimagic total labeling on \(G\) is a one-to-one map \(f\) from \(V(G) \cup E(G)\) onto the integers \(1, 2, \ldots, |V(G)| + |E(G)|\) with the property that the edge-weights \(w(uv) = f(u) + f(v) + f(uv)\), \(uv \in E(G)\), form an arithmetic progression starting from \(a\) and having common difference \(d\). Such a labeling is called super if the smallest labels appear on the vertices. In this paper, we investigate the existence of super \((a, d)\)-edge-antimagic total labelings of disjoint union of multiple copies of complete bipartite graph.

Let \(G = (V, E)\) be a graph with no isolated vertex. A classical observation in domination theory is that if \(D\) is a minimum dominating set of \(G\), then \(V \setminus D\) is also a dominating set of \(G\). A set \(D’\) is an inverse dominating set of \(G\) if \(D’\) is a dominating set of \(G\) and \(D’ \subseteq V \setminus D\) for some minimum dominating set \(D\) of \(G\). The inverse domination number of \(G\) is the minimum cardinality among all inverse dominating sets of \(G\). The independence number of \(G\) is the maximum cardinality of an independent set of vertices in \(G\). Domke, Dunbar, and Markus (Ars Combin. \(72 (2004), 149-160)\) conjectured that the inverse domination number of \(G\) is at most the independence number of \(G\). We prove this conjecture for special families of graphs, including claw-free graphs, bipartite graphs, split graphs, very well covered graphs, chordal graphs, and cactus graphs.

A \(\lambda\)-design on \(v\) points is a set of \(v\) distinct subsets (blocks) of a \(v\)-set such that any two different blocks meet in exactly \(\lambda\) points and not all of the blocks have the same size. Ryser’s and Woodall’s \(\lambda\)-design conjecture states that every \(\lambda\)-design can be obtained from a symmetric design by a certain complementation procedure. A result of Ryser and Woodall establishes that there exist two integers, \(r\) and \(r^*\), such that each point in a \(\lambda\)-design is in exactly \(r\) or \(r^*\) blocks. The main result of the present paper is that the \(\lambda\)-design conjecture is true for \(\lambda\)-designs with \(\gcd(r-1,r^*-1)=7\).

Improving on Domokos’s improvement of Swan’s theorem, we show that under certain conditions on a finite digraph, whenever \(p,q\) are vertices, then the number of even Eulerian paths from \(p\) to \(q\) is the same as the number of odd ones from \(p\) to \(q\).