In this paper, we give some new identities of symmetry for \(q\)-Bernoulli polynomials under the symmetric group of degree \(n\) arising from \(p\)-adic \(q\)-integrals on \(\mathbb{Z}_p\).

The covering and packing of a unit square (resp. cube) with squares (resp. cubes) are considered. In \(d\)-dimensional Euclidean space \(\mathbb{E}^d\), the size of a \(d\)-hypercube is given by its side length and the size of a covering is the total size of the \(d\)-hypercubes used to cover the unit hypercube. Denote by \(g_d(n)\) the smallest size of a minimal covering (consisting of \(n\) hypercubes) of a \(d\)-dimensional unit hypercube. In this paper, we consider the problem of covering a unit hypercube with hypercubes in \(\mathbb{E}^d\) for \(d \geq 4\) and determine the tight upper bound and lower bound for \(g_d(n)\).

Given the binomial transforms \(\{b_n\}\) and \(\{c_n\}\) of the sequences \(\{a_n\}\) and \(\{d_n\}\) correspondingly, we compute the binomial transform of the sequence \(\{a_nc_n\}\) in terms of \(\{b_n\}\) and \(\{d_n\}\). In particular, we compute the binomial transform of the sequences \(\{n{n-1}\ldots (n-1-m)a_n\}\) and \(\{a_k x^k\}\) in terms of \(\{b_n\}\). Further applications include new binomial identities with the binomial transforms of the products \(H_n B_n\), \(H_n F_n\), \(H_n L_n(X)\), and \(B_n F_n\), where \(H_n\), \(B_n\), \(F_n\), and \(L_n(X)\) are correspondingly the harmonic numbers, the Bernoulli numbers, the Fibonacci numbers, and the Laguerre polynomials.

A kite graph is a graph obtained from a \(3\)-cycle (or triple) by adding a pendent edge to a vertex of the \(3\)-cycle. A kite system of order \(v\) is a pair \((X, \mathcal{B})\), where \(\mathcal{B}\) is an edge-disjoint collection of kite graphs which partitions the edge set of \(K_v\). A kite system of order \(v\) is cyclic if it admits an automorphism of order \(v\), and 1-rotational if it admits an automorphism containing one fixed point and a cycle of length \(v – 1\). In this paper, we show that there exists a cyclic kite system of order \(v\) if and only if \(v \equiv 1 \pmod{8}\), and there exists a \(1\)-rotational kite system of order \(v\) if and only if \(v \equiv 0 \pmod{8}\).

A \(2\)-rainbow dominating function (2RDF) on a graph \(G = (V, E)\) is a function \(f\) from the vertex set \(V\) to the set of all subsets of the set \(\{1,2\}\) such that for any vertex \(v \in V\) with \(f(v) = \emptyset\) the condition \(\cup_{u \in N(v)} f(u) = \{1, 2\}\) is fulfilled. The weight of a 2RDF \(f\) is the value \(w(f) = \sum_{v \in V(G)} |f(v)|\). The \(2\)-rainbow domination number, denoted by \(\gamma_{r2}(G)\), is the minimum weight of a 2RDF on \(G\). The rainbow bondage number \(b_{r2}(G)\) of a graph \(G\) with maximum degree at least two, is the minimum cardinality of all sets \(E’ \subseteq E(G)\) for which \(\gamma_{r2}(G – E’) > \gamma_{r2}(G)\). Dehgardi, Sheikholeslami, and Volkmann [Discrete Appl. Math. \(174 (2014), 133-139]\) proved that the rainbow bondage number of a planar graph does not exceed 15. In this paper, we improve this result.

Let \(id(v)\) denote the implicit degree of a vertex \(v\) in a graph \(G\). We define \(G\) to be implicit claw-heavy if every induced claw of \(G\) has a pair of nonadjacent vertices such that their implicit degree sum is more than or equal to \(|V(G)|\). In this paper, we show that an implicit claw-heavy graph \(G\) is hamiltonian if we impose certain additional conditions on \(G\) involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Chen et al. [B. Chen, 8. Zhang and S. Qiao, Hamilton cycles in claw-heavy graphs, Discrete Math., \(309 (2009) 2015-2019.]\) on the existence of Hamilton cycles in claw-heavy graphs.

A connected graph \(G\) is called a quasi-tree graph, if there exists \(v_0 \in V(G)\) such that \(G – v_0\) is a tree. In this paper, among all triangle-free quasi-tree graphs of order \(n\) with \(G – v_0\) being a tree and \(d(v_0) = d(v_0)\), we determine the maximal and the second maximal signless Laplacian spectral radii together with the corresponding extremal graphs. By an analogous manner, we obtain similar results on the spectral radius of triangle-free quasi-tree graphs.

The notation \(tK_3\) represents a graph with \(t\) copies of the complete graph \(K_3\). In this note, we discuss the goodness of path \(P_n\) or cycle \(C_n\) with respect to \(tK_3\). Furthermore, this result provides the computation of Ramsey number \(R(G, tK_3)\) when \(G\) is a set of disjoint paths or cycles.

A \(k\)-king in a digraph \(D\) is a vertex which can reach every other vertex by a directed path of length at most \(k\). Every tournament with no vertex of in-degree zero has at least three \(2\)-kings. In this paper, we present the structure of tournaments which have exactly three \(2\)-kings and prove that every strong tournament, containing at least \(k+2\) vertices with \(k \geq 3\), has at least \(k+1\) \(k\)-kings.

A kernel in a directed graph \(D(V, E)\) is a set \(S\) of vertices of \(D\) such that no two vertices in \(S\) are adjacent and for every vertex \(u\) in \(V \setminus S\) there is a vertex \(v\) in \(S\), such that \((u,v)\) is an arc of \(D\). The definition of kernel implies that the vertices in the kernel form an independent set. If the vertices of the kernel induce an independent set of edges, we obtain a variation of the definition of the kernel, namely a total-kernel. The problem of existence of a kernel is itself an NP-complete problem for a general digraph. But in this paper, we solve the strong total-kernel problem of an oriented Circular Ladder and Möbius Ladder in polynomial time.

For two vertices \(u\) and \(v\) of a nontrivial connected graph \(G\), the set \(I[u,v]\) consists of all vertices lying on some \(u-v\) geodesic in \(G\), including \(u\) and \(v\). For \(S \subseteq V(G)\), the set \(Z[S]\) is the union of all sets \(I[u,v]\) for \(u,v \in S\). A set \(S \subseteq V(G)\) is a connected geodetic set of \(G\) if \(Z[S] = V(G)\) and the subgraph in \(G\) induced by \(S\) is connected. The minimum cardinality of a connected geodetic set of \(G\) is the connected geodetic number \(g_c(G)\) of \(G\) and a connected geodetic set of \(G\) whose cardinality equals \(g_c(G)\) is a minimum connected geodetic set of \(G\). A subset \(T\) of a minimum connected geodetic set \(S\) is a forcing subset for \(S\) if \(S\) is the unique minimum connected geodetic set of \(G\) containing \(T\). The forcing connected geodetic number \(f(S)\) of \(S\) is the minimum cardinality of a forcing subset of \(S\) and the forcing connected geodetic number \(f(G)\) of \(G\) is the minimum forcing connected geodetic number among all minimum connected geodetic sets of \(G\). Therefore, \(0 \leq f_c(G) \leq g_c(G)\). We determine all pairs \((a,b)\) of integers such that \(f_c(G) = a\) and \(gc(G) = b\) for some nontrivial connected graph \(G\). We also consider a problem of realizable triples of integers.

Hovey [11] called a graph \(G\) \(A\)-cordial, where \(A\) is an additive Abelian group, and \(f: V(G) \to A\) is a labeling of the vertices of \(G\) with elements of \(A\) such that when the edges of \(G\) are labeled by the induced labeling \(f: E(G) \to A\) by \(f^*(xy) = f(x) + f(y)\), then the number of vertices (resp. edges) labeled with \(\alpha\) and the number of vertices (resp. edges) labeled with \(\beta\) differ by at most one for all \(\alpha, \beta \in A\). When \(A = \mathbb{Z}_k\), we call a graph \(G\) \(k\)-cordial instead of \(\mathbb{Z}_k\)-cordial. In this paper, we give a sufficient condition for the join of two \(k\)-cordial graphs to be \(k\)-cordial and we give also a necessary condition for certain Eulerian graphs to be \(k\)-cordial when \(k\) is even, and finally we complete the characterization of the \(4\)-cordiality of the complete tripartite graph.

Let \(*\) be a binary graph operation. We call \(*\) a Cayley operation if \(\Gamma_1 * \Gamma_2\) is a Cayley graph for any two Cayley graphs \(\Gamma_1\) and \(\Gamma_2\) . In this paper, we prove that the Cartesian, (categorical or tensor) direct, and lexicographic products are Cayley operations. We also investigate the following question: Under what conditions on a binary graph operation \(*\) and Cayley graphs \(\Gamma_1\) and \(\Gamma_2\), the graph product \(\Gamma_1 * \Gamma_2\) is again a Cayley graph. The latter question is studied for the union, join (sum), replacement, and zig-zag products of graphs.

Let \(R(G)\) be the graph obtained from \(G\) by adding a new vertex corresponding to each edge of \(G\) and by joining each new vertex to the end vertices of the corresponding edge. Let \(RT(G)\) be the graph obtained from \(R(G)\) by adding a new edge corresponding to every vertex of \(G\), and by joining the end vertices of each new edge to the corresponding vertex of \(G\). In this paper, we determine the Laplacian polynomials of \(RT(G)\) of a regular graph \(G\). Moreover, we derive formulae and lower bounds of Kirchhoff indices of the graphs. Finally, we also present the formulae for calculating the Kirchhoff indices of some special graphs as applications, which show the correction and efficiency of the proposed results.

For integer \(n \geq 2\), let \(a_1, a_2, a_3, \ldots, a_n\) be an increasing sequence of nonnegative integers, and define the \(n\)-star \(St(a_1, a_2, \ldots, a_n)\) as the disjoint union of the \(n\) star graphs \(K(1, a_1), K(1, a_2), \ldots, K(1, a_n)\). In this paper, we have partially settled the conjecture by Lee and Kong [4] that says for any odd \(n \geq 3\), the \(n\)-star \(St(a_1, a_2, \ldots, a_n)\) is super edge magic. We solve the two cases:

1. The \(n\)-star \(St(a_1, a_2, \ldots, a_n)\) is super edge magic where \(a_i = 1 + (i – 1)d\) for all integers \(1 \leq i \leq n\) and \(d\) is any positive integer.

2. An \(n\)-star \(St(a_1, a_2, \ldots, a_n)\) is not super edge magic when \(a_1 = 0\).

Let \(G\) be a simple connected graph with the vertex set \(V(G)\). The eccentric distance sum of \(G\) is defined as \(\xi^d(G) = \sum_{v \in V(G)} \varepsilon(v) D_G(v)\), where \(\varepsilon(v)\) is the eccentricity of the vertex \(v\) and \(D_G(v)\) is the sum of all distances from the vertex \(v\). The Harary index of \(G\) is defined as \(H(G) = \sum_{u,v \in V(G)} \frac{1}{d(u, v)}\), where \(d(u, v)\) is the distance between \(u\) and \(v\) in \(G\). The degree powers of \(G\) is defined as \(H(G) = \sum_{|u,v| \subseteq V(G)} \frac{1}{d(u,v)}\) for the natural number \(p \geq 1\). In this paper, we determine the extremal graphs with the minimal eccentric distance sum, the maximal Harary index, and the maximal degree powers among all graphs with given diameter.

Let \(\Gamma(V, E)\) be a graph of order \(n\), \(S \subset V\), and let \(B(S)\) be the set of vertices in \(V \setminus S\) that have a neighbor in \(S\). The differential of a set \(S\) is defined as \(\partial(S) = |B(S)| – |S|\), and the differential of the graph \(\Gamma\) is defined as \(\partial(\Gamma) = \max\{\partial(S) : S \subset V\}\). In this paper, we obtain several tight bounds for the differential in Cartesian product graphs. In particular, we relate the differential in Cartesian product graphs with some known parameters of \(\Gamma_1 \times \Gamma_2\), namely, its domination number, its maximum and minimum degree, and its order. Furthermore, we compute explicitly the differential of some classes of product graphs.

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.

In the paper, we discuss properties of the (super) vertex-graceful labeling of cycle \(C_n\), crown graph \(C_n \odot K_1\), and generalized crown graph \(C_n \odot K_{1,t}\), and prove that \(C_n\), \(C_{n} \odot K_1\), and \(C_n \odot K_{1,t}\) are vertex-graceful if \(n\) is odd; \(C_n\) is super vertex-graceful if \(n \neq 4, 6\); and \(C_{n} \odot K_1\) is super vertex-graceful if \(n\) is even. Moreover, we propose two conjectures on (super)vertex-graceful labeling.

For any integer \(m \geq 2\), let \(\mu_m\) be the group of \(m\)th roots of unity. Let \(p\) be a prime and \(a\) a positive integer. For \(m = p^\alpha\), it is shown that there is no \(n \times n\) matrix over \(\mu_m\) with vanishing permanent if \(n < p\).

A subset \(S \subseteq V(G)\) is an independent dominating set for \(G\) if \(S\) is independent and each vertex of \(G\) is either in \(S\) or adjacent to some vertex of \(S\). Let \(i(G)\) denote the minimum cardinality of an independent dominating set for \(G\). For a positive integer \(t\), a graph \(G\) is \(t\)-i-critical if \(i(G) = t\), but \(i(G + uv) < t\) for any pair of non-adjacent vertices \(u\) and \(v\) of \(G\). Further, for a positive integer \(k\), a graph \(G\) is \(k\)-factor-critical if for every \(S \subseteq V(G)\) with \(|S| = k\), \(G – S\) has a perfect matching. In this paper, we provide sufficient conditions for connected \(3\)-i-critical graphs to be \(k\)-factor-critical in terms of connectivity and minimum degree.

Let \(G = (V, E)\) be a simple graph, \(I(G)\) its incidence matrix. The incidence energy of \(G\), denoted by \(IE(G)\), is the sum of the singular values of \(I(G)\). The incidence energy \(IE(G)\) of a graph is a recently proposed quantity. However, \(IE(G)\) is closely related with the eigenvalues of the Laplacian and signless Laplacian matrices of \(G\). The trees with the maximal, the second maximal, the third maximal, the smallest, the second smallest, and the third smallest incidence energy were characterized. In this paper, the trees with the fourth and fifth smallest incidence energy are characterized by the quasi-order method and Coulson integral formula, respectively. In addition, the fourth maximal incidence energy among all trees on \(n\) vertices is characterized.

A Roman dominating function (or simply RDF) on a graph \(G = (V(G), E(G))\) is a labeling \(f: V(G) \to \{0, 1, 2\}\) satisfying the condition that every vertex with label \(0\) has at least a neighbor with label \(2\). The Roman domination number, \(\gamma_R(G)\), of \(G\) is the minimum of \(\sum_{v \in V(G)} f(v)\) over such functions. The Roman bondage number, \(b_R(G)\), of a graph \(G\) with maximum degree at least two is the minimum cardinality among all sets \(E \subseteq E(G)\) for which \(\gamma_R(G – E) > \gamma_R(G)\). It was conjectured that if \(G\) is a graph of order \(n\) with maximum degree at least two, then \(b_R(G) \leq n – 1\). In this paper, we settle this conjecture. More precisely, we prove that for every connected graph of order \(n \geq 3\), \(b_R(G) \leq \min\{n – 1, n – \gamma_R(G) + 5\}\).

Let \(G\) be a finite and simple graph with vertex set \(V(G)\), and let \(f: V(G) \to \{-1, 1\}\) be a two-valued function. If \(k \geq 1\) is an integer and \(\sum_{x\in N[v]}f(x) \geq k\) for each \(v \in V(G)\), where \(N[v]\) is the closed neighborhood of \(v$, then \(f\) is a signed \(k\)-dominating function on \(G\). A set \(\{f_1, f_2, \ldots, f_d\}\) of distinct signed \(k\)-dominating functions on \(G\) with the property that \(\sum_{i=1}{d}f_i(v) \leq j\) for each \(x \in V(G)\), is called a signed \((j, k)\)-dominating family (of functions) on \(G\), where \(j \geq 1\) is an integer. The maximum number of functions in a signed \((j, k)\)-dominating family on \(G\) is the signed \((j, k)\)-domatic number on \(G\), denoted by \(d_{jkS}(G)\).

The aim of this paper is to classify the vertex-primitive symmetric graphs of order \(6p\). These works were essentially done in \([1]\). But in \([1]\) there is no such situation: \(G = \mathrm{PSL}(2, 13)\) acting on the set of cosets of subgroup \(H \cong D_{14}\). Then \(m = |\Omega| = 78 = 6p\), \(G\) has rank \(9\), and the sub-orbits of \(G\) have one of length \(1\), five of length \(7\), and three of length \(14\). In this paper, we give a complete list of symmetric graphs of order \(6p\).

Let \(p\) be an odd prime and \(n\) be a positive integer. For any positive integer \(d \leq n\), let \(g_1(x) = 1 + x^{p^{n-d}} + x^{{2p}^{n-d}} + \ldots + x^{(p-1)p^{n-d}}\) and \(g_2(x) = 1 + x^{p^{n-d+1}} + x^{2p^{n-d+1}} + \ldots + x^{{(p^{d-1}-1)}{p^{n-d+1}}}\). In this paper, we provide a method to determine the weight distributions of binary cyclic codes of length \(p^n\) generated by the polynomials \(g_1(x)\) and \(g_01(x)g_2(x)\), which is effective for small values of \(p\) and \(d\).

A spanning tree with no vertices of degree two of a graph is called a homeomorphically irreducible spanning tree (or HIST) of the graph. It has been proved that every planar triangulation \(G\) with at least four vertices has a HIST \(H\) [1]. However, the previous result asserts nothing whether the degree of a fixed vertex \(v\) of \(G\) is at least three or not in \(H\). In this paper, we prove that if a planar triangulation \(G\) has \(2n\) (\(n \geq 2\)) vertices, then, for any vertex \(v\), \(G\) has a HIST \(H\) such that the degree of \(v\) is at least three in \(H\). We call such a spanning tree a rooted HIST of \(G\) with root \(v\).

A graph \(G\) is Hamiltonian connected, if there is a Hamiltonian path between every two distinct vertices of \(G\). A Hamiltonian connected graph \(G\) is called critical Hamiltonian connected (CHC), if for every edge \(e\) in \(G\), the graph \(G – e\) is not Hamiltonian connected. In this paper, we study the properties of CHC graphs.

A generalized \(\theta\)-graph is composed of at least three internal disjoint paths (at most one of them is with length 1) which have the same initial vertex and the same terminal vertex. If the initial vertex and the terminal vertex are the same in a generalized \(\theta\)-graph, then the generalized \(\theta\)-graph is called a degenerated \(\theta\)-graph or a petal graph. In this paper, two graft transformations that increase or decrease the \(Q\)-spectral radius of a graph are represented. With them, for the generalized \(\theta\)-graphs and petal graphs with order \(n\), the extremal graphs with the maximal \(Q\)-spectral radius and the extremal graphs with the minimal \(Q\)-spectral radius are characterized, respectively.