The necessary and sufficient conditions for a given sequence of positive integers \(d_1, d_2, \ldots, d_n\) to be the degree sequence of \(3\)-connected graphs and cactus graphs are proved respectively by S. L. Hakimi [5] and A. R. Rao [6]. In this note, we utilize these results to prove a formula for the functions \(d_{tc}(2m)\) and \(d_{ca}(2m)\), the number of degree sequences with degree sum \(2m\) by \(3\)-connected graphs and cactus graphs respectively. We give generating function proofs and elementary proofs of the formulas \(d_{tc}(2m)\) and \(d_{ca}(2m)\).

In this paper, the graphs with maximal (signless Laplacian) spectral radius among all connected graphs with given matching number are characterized.

Let \(c\) be a proper \(k\)-coloring of a connected graph \(G\) and \(\Pi = (V_1, V_2, \ldots, V_k)\) be an ordered partition of \(V(G)\) into the resulting color classes. For a vertex \(v\) of \(G\), the color code of \(v\) with respect to \(\Pi\) is defined to be the ordered \(k\)-tuple \(c_\Pi := (d(v, V_1), d(v, V_2), \ldots, d(v, V_k))\), where \(d(v, V_i) = \min\{d(v, x) \mid x \in V_i\}\) for \(1 \leq i \leq k\). If distinct vertices have distinct color codes, then \(c\) is called a locating coloring. The minimum number of colors needed in a locating coloring of \(G\) is the locating chromatic number of \(G\), denoted by \(\chi_L(G)\). In this paper, we study the locating chromatic numbers of grids, the cartesian product of paths and complete graphs, and the cartesian product of two complete graphs.

A graph \(\Gamma\) is said to be \((G, 2)\)-distance-transitive if, for \(i = 1, 2\) and for any two vertex pairs \((u_1, v_1)\) and \((u_2, v_2)\) with \(d_\Gamma(u_1, v_1) = d_\Gamma(u_2, v_2) = i\), there exists \(g \in G\) such that \((u_1, v_1)^g = (u_2, v_2)\). This paper classifies the family of \((G, 2)\)-distance-transitive graphs of valency \(7\).

We investigate the group choice number of a graph \(G\) and prove the group list coloring version of Brooks’ Theorem, the group list coloring version of Szekeres-Wilf extension of Brooks’ Theorem, and the Nordhaus-Gaddum inequalities for group choice numbers. Furthermore, we characterize all \(D\)-group choosable graphs and all \(3\)-group choosable complete bipartite graphs.

We study a poset of compositions restricted by part size under a partial ordering introduced by Björner and Stanley. We show that our composition poset \(C_{n, k}\) is isomorphic to the poset of words \(A_{d}^{*}\). This allows us to use techniques developed by Björner to study the Möbius function of \(C_{d+1}\). We use counting arguments and shellability as avenues for proving that the Möbius function is \(\mu(u, w) = (-1)^{|u|+|w|}{\binom{w}{u}}_{dn}\), where \({\binom{w}{u}}_{dn}\) is the number of \(d\)-normal embeddings of \(u\) in \(w\). We then prove that the formal power series whose coefficients are given by the zeta and the Möbius functions are both rational. Following in the footsteps of Björner and Reutenauer and Björner and Sagan, we rely on definitions to prove rationality in one case, and in another case we use finite-state automata.

The distribution of the set of embeddings of a graph into orientable or non-orientable surfaces is called the total embedding distribution. Chen, Gross, and Rieper [Discrete Math. \(128(1994) 73-94.]\) first used the overlap matrix for calculating the total embedding distributions of necklaces, closed-end ladders, and cobblestone paths. In this paper, also by using the overlap matrix, closed formulas of the total embedding distributions for two classes of graphs are given.

In this paper, we obtained two flag-transitive symmetric \((v, k, \lambda)\) designs admitting primitive automorphism groups of almost simple type with socle \(X = \mathrm{PSL}(12, 2)\).

In this paper, we present a new combinatorial problem, called the Nearly Perfect Bipartition Problem, which is motivated by a computer networks application. This leads to a new graph parameter, \(PN_p(G)\), which equals the maximum cardinality of a proper nearly perfect set. We show that the corresponding decision problem is \(NP\)-hard, even when restricted to graphs of diameter \(3\). We present several bounds for \(PN_p(G)\) and determine the value of \(PN_p(G)\) for several classes of graphs.

In this paper we determine the exact values of the signed domination number, signed total domination number, and minus domination number of complete multipartite graphs, which substantially generalizes some previous results obtained for special subclasses of complete multipartite graphs such as cliques and complete bipartite graphs.