A vertex \(k\)-ranking of a graph \(G\) is a function \(c: V(G) \to \{1,\ldots,k\}\) such that if \(c(u) = c(v)\), \(u,v \in V(G)\), then each path connecting vertices \(u\) and \(v\) contains a vertex \(w\) with \(c(w) > c(u)\). If each vertex \(v\) has a list of integers \(L(v)\) and for a vertex ranking \(c\) it holds \(c(v) \in L(v)\) for each \(v \in V(G)\), then \(c\) is called an \(L\)-list \(k\)-ranking, where \(\mathcal{L} = \{L(v) : v \in V(G)\}\). In this paper, we investigate both vertex and edge (vertex ranking of a line graph) list ranking problems. We prove that both problems are NP-complete for several classes of acyclic graphs, like full binary trees, trees with diameter at most \(4\), and comets. The problem of finding vertex (edge) \(\mathcal{L}\)-list ranking is polynomially solvable for paths and trees with a bounded number of non-leaves, which includes trees with diameter less than \(4\).

In this paper we determine unique graph with largest spectral radius among all tricyclic graphs with \(n\) vertices and \(k\) pendant edges.

A new proof is given to the following result of ours. Let \(G\) be an outerplanar graph with maximum degree \(\Delta \geq 3\). The chromatic number \(\chi(G^2)\) of the square of \(G\) is at most \(\Delta+2\), and \(\chi(G^2) = \Delta+1\) if \(\Delta \geq 7\).

Some designs using the action of the linear fractional groups \(L_2(q)\), \(q = 11, 13, 16, 17, 19, 23\) are constructed. We will show that \(L_2(q)\) or its automorphism group acts as the full automorphism group of each of the constructed designs except in the case \(q = 16\). For designs constructed from \(L_2(16)\), we will show that \(L_2(16)\), \(L_2(16) : 2\), \(L_2(16) : 4\) or \(S_{17}\) can arise as the full automorphism group of the design.

For odd \(n \geq 5\), the Flower Snark \(F_n = (V, E)\) is a simple undirected cubic graph with \(4n\) vertices, where \(V = \{a_i : 0 \leq i \leq n-1\} \cup \{b_i : 0 \leq i \leq n-1\} \cup \{c_i : 0 \leq i \leq 2n-1\}\) and \(E = \{b_ib_{(i+1)\mod(n)}: 0 \leq i \leq n-1\} \cup \{c_ic_{(i+1)\mod(2n)} : 0 \leq i \leq 2n-1\} \cup \{a_ib_i,a_ic_i,a_ic_{n+i} : 0 \leq i \leq n-1\}\). For \(n = 3\) or even \(n \geq 4\), \(F_n\) is called the related graph of Flower Snark. We show that the crossing number of \(F_n\) equals \(n – 2\) if \(3 \leq n \leq 5\), and \(n\) if \(n \geq 6\).

A subset \(S\) of the vertex set of a graph \(G\) is called acyclic if the subgraph it induces in \(G\) contains no cycles. We call \(S\) an acyclic dominating set if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by \(\gamma_a(G)\), is called the acyclic domination number of \(G\). A graph \(G\) is \({2-diameter-critical}\) if it has diameter \(2\) and the deletion of any edge increases its diameter. In this paper, we show that for any positive integers \(k\) and \(d \geq 3\), there is a \(2\)-diameter-critical graph \(G\) such that \(\delta(G) = d\) and \(\gamma_a(G) – \delta(G) \geq k\), and our result answers a question posed by Cheng et al. in negative.

A function \(f: V \to \{1,\ldots,k\}\) is a broadcast coloring of order \(k\) if \(\pi(u) = \pi(v)\) implies that the distance between \(u\) and \(v\) is more than \(\pi(u)\). The minimum order of a broadcast coloring is called the broadcast chromatic number of \(G\), and is denoted \(\chi_b(G)\). In this paper we introduce this coloring and study its properties. In particular, we explore the relationship with the vertex cover and chromatic numbers. While there is a polynomial-time algorithm to determine whether \(\chi_b(G) \leq 3\), we show that it is \(NP\)-hard to determine if \(\chi_b(G) \leq 4\). We also determine the maximum broadcast chromatic number of a tree, and show that the broadcast chromatic number of the infinite grid is finite.

A connected graph \(G = (V, E)\) is said to be \((a,d)\)-antimagic if there exist positive integers \(a,d\) and a bijection \(f : E \to \{1,2,\ldots,|E|\}\) such that the induced mapping \(g_f : V \to \mathbb{N}\), defined by \(g_f(v) = \sum f(uv)\),\({uv \in E(G)}\) is injective and \(g_f(V) = \{a,a+d,\ldots,a+(|V|-1)d\}\). Mirka Miller and Martin Bača proved that the generalized Petersen graph \(P(n, 2)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for \(n \equiv 0 \pmod{4}\), \(n \geq 8\) and conjectured that the generalized Petersen graph \(P(n, k)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n\) and \(2 \leq k \leq \frac{n}{2}-1\). In this paper, we show that the generalized Petersen graph \(P(n, 3)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n \geq 8\).

In this paper, we derive new recurrence relations and generating matrices for the sums of usual Tribonacci numbers and \(4n\) subscripted Tribonacci sequences, \(\{T_{4n}\}\), and their sums. We obtain explicit formulas and combinatorial representations for the sums of terms of these sequences. Finally, we represent relationships between these sequences and permanents of certain matrices.

Let \(\mathcal{K} = (K_{ij})\) be an infinite lower triangular matrix of non-negative integers such that \(K_{i0} = 1\) and \(K_{ii} \geq 1\) for \(i \geq 0\). Define a sequence \(\{V_i(\mathcal{K})\}_{m\geq0}\) by the recurrence \(V_{i+1}(\mathcal{K}) = \sum_{j=0}^m K_{mj}V_j(\mathcal{K})\) with \(V_0(\mathcal{K}) = 1\). Let \(P(n;\mathcal{K})\) be the number of partitions of \(n\) of the form \(n = p_1 + p_2 + p_3 + p_4 + \cdots\) such that \(p_j \geq \sum_{i\geq j} K_{ij}p_{i+1}\) for \(j \geq 1\) and let \(P(n;V(\mathcal{K}))\) denote the number of partitions of \(n\) into summands in the set \(V(\mathcal{K}) = \{V_1(\mathcal{K}), V_2(\mathcal{K}), \ldots\}\). Based on the technique of MacMahon’s partitions analysis, we prove that \(P(n;\mathcal{K}) = P(n;V(\mathcal{K}))\) which generalizes a recent result of Sellers’. We also give several applications of this result to many classical sequences such as Bell numbers, Fibonacci numbers, Lucas numbers, and Pell numbers.