In this paper, we introduce \(h(x)\)-Lucas quaternion polynomials that generalize \(k\)-Lucas quaternion numbers that generalize Lucas quaternion numbers. Also we derive the Binet formula and generating function of \(h(x)\)-Lucas quaternion polynomial sequence.

We determine the crossing numbers (i) of the complete graph \(K_n\) with an edge deleted for \(n \leq 12\) and (ii) of the complete bipartite graph \(K_{m,n}\) with an edge deleted for \(m \in \{3,4\}\) and for all natural numbers \(n$\), and also for the case \(m = n = 5\).

A \(G\)-design is called balanced if the degree of each vertex \(x\) is a constant. A \(G\)-design is called strongly balanced if for every \(i = 1, 2, \ldots, h\), there exists a constant \(C_i\) such that \(d_{A_i}(x) = C_i\) for every vertex \(x\), where \(A_i\) are the orbits of the automorphism group of \(G\) on its vertex-set and \(d_{A_i}(x)\) of a vertex is the number of blocks containing \(x\) as an element of \(A_i\). We say that a \(G\)-design is simply balanced if it is balanced, but not strongly balanced. In this paper, we determine the spectrum for simply balanced and strongly balanced House-systems. Further, we determine the spectrum for House-systems of all admissible indices nesting \(C_4\)-systems.

The Wiener index of a graph is the sum of the distances between all pairs of vertices. In this paper, we determine \(h\)-cacti and \(h\)-cactus chains with the extremal Wiener indices, respectively.

A cyclic coloring is a vertex coloring such that vertices incident with the same face receive different colors. Let \(G\) be a plane graph, and let \(\Delta^*\) be the maximum face degree of \(G\). In 1984, Borodin conjectured that every plane graph admits a cyclic coloring with at most \(\left\lfloor \frac{3\Delta^*}{2} \right\rfloor\) colors. In this note, we improve a result of Borodin et al. [On cyclic colorings and their generalizations, Discrete Mathematics 203 (1999), 23-40] by showing that every plane graph with \(\Delta^* = 6\) can be cyclically colored with 9 colors. This confirms the Cyclic Coloring Conjecture in the case \(\Delta^* = 6\).

In this paper, we derive some identities involving Genocchi polynomials and numbers. These identities follow by evaluating a certain integral in various ways. Also, we express the product of two Genocchi polynomials as a linear combination of Bernoulli polynomials.

Fuzzy graph theory is finding an increasing number of applications in modeling real-time systems where the level of information inherent in the system varies with different levels of precision. Fuzzy models are becoming useful because of their aim in reducing the differences between the traditional numerical models used in engineering and sciences, and the symbolic models used in expert systems. A bipolar fuzzy model is a generalized soft computing model of a fuzzy model that gives more precision, flexibility, and compatibility to a system when compared with systems designed using fuzzy models. In this research article, we introduce certain types of bipolar fuzzy competition graphs, including bipolar fuzzy \(k\)-competition, bipolar fuzzy \(p\)-competition, and bipolar fuzzy \(m\)-competition. We investigate some properties of these new concepts.

The \(\alpha\)-incidence energy of a graph is defined as the sum of \(a\)th powers of the signless Laplacian eigenvalues of the graph, where \(a\) is a real number such that \(\alpha \neq 0\) and \(\alpha \neq 1\). The \(\alpha\)-distance energy of a graph is defined as the sum of \(a\)th powers of the absolute values of the eigenvalues of the distance matrix of the graph, where \(\alpha\) is a real number such that \(\alpha \neq 0\). In this note, we present some bounds for the \(\alpha\)-incidence energy of a graph. We also present some bounds for the \(\alpha\)-distance energy of a tree.

Multi-sender authentication codes allow a group of senders to construct an authenticated message for a receiver such that the receiver can verify authenticity of the received message. In this paper, we construct one multi-sender authentication codes from
polynomials over finite fields. Some parameters and the probabilities of deceptions of this codes are also computed.

A graph \(G\) is called \((k, d)^*\)-choosable if for every list assignment \(L\) satisfying \(|L(v)| \geq k\) for all \(v \in V(G)\), there is an \(L\)-coloring of \(G\) such that each vertex of \(G\) has at most \(d\) neighbors colored with the same color as itself. In this paper, it is proved that every graph of nonnegative characteristic without \(4\)-cycles and intersecting triangles is \((3, 1)^*\)-choosable.

In this paper, we study \((2-d)\)-kernels in graphs. We shall show that the problem of the existence of \((2-d)\)-kernels is \(\mathcal{N}P\)-complete for a general graph. We also give some results related to the problem of counting \((2-d)\)-kernels in graphs. For special graphs, we show that the number of \((2-d)\)-kernels is equal to the Fibonacci numbers.

In 1989, Frankl and Füredi [1] conjectured that the \(r\)-uniform hypergraph with \(m\) edges formed by taking the first \(m\) sets in the colex ordering of \(\mathbb{N}^{(r)}\) has the largest Lagrangian of all \(r\)-uniform hypergraphs of size \(m\). For \(2\)-graphs, the Motzkin-Straus theorem implies this conjecture is true. For \(3\)-uniform hypergraphs, it was proved by Talbot in 2002 that the conjecture is true while \(m\) is in a certain range. In this paper, we prove that the \(4\)-uniform hypergraphs with \(m\) edges formed by taking the first \(m\) sets in the colex ordering of \(\mathbb{N}^{(r)}\) has the largest Lagrangian of all \(4\)-uniform hypergraphs with \(t\) vertices and \(m\) edges satisfying \(\binom{t-1}{4} \leq m \leq \binom{t-1}{4} + \binom{t-2}{3} – 17\binom{t-2}{2} + 1\).

A graph \(G\) on \(n \geq 3\) vertices is called claw-heavy if every induced claw of \(G\) has a pair of nonadjacent vertices such that their degree sum is at least \(n\). We say that a subgraph \(H\) of \(G\) is \(f\)-heavy if \(\max\{d(x), d(y)\} \geq \frac{n}{2}\) for every pair of vertices \(x, y \in V(H)\) at distance \(2\) in \(H\). For a given graph \(R\), \(G\) is called \(R\)-\(f\)-heavy if every induced subgraph of \(G\) isomorphic to \(R\) is \(f\)-heavy. For a family \(\mathcal{R}\) of graphs, \(G\) is called \(\mathcal{R}\)-\(f\)-heavy if \(G\) is \(R\)-\(f\)-heavy for every \(R \in \mathcal{R}\). In this paper, we show that every \(2\)-connected claw-heavy graph is hamiltonian if \(G\) is \(\{P_7, D\}\)-\(f\)-heavy, or \(\{P_7, H\}\)-\(f\)-heavy, where \(D\) is a deer and \(H\) is a hourglass. Our result is a common generalization of previous theorems of Broersma et al. and Fan on hamiltonicity of \(2\)-connected graphs.

An \(H_3\) graph is a multigraph on three vertices with double edges between two pairs of distinct vertices and a single edge between the third pair. In this paper, we decompose a complete multigraph \(2K_{10t}\) into \(H_3\) graphs.

In 1989, Zhu, Li, and Deng introduced the definition of implicit degree, denoted by \(\text{id}(v)\), of a vertex \(v\) in a graph \(G\). In this paper, we give a simple method to prove that: if \(G\) is a \(k\)-connected graph of order \(n\) such that the implicit degree sum of any \(k+1\) independent vertices is more than \((k+1)(n-1)/2\), then \(G\) is hamiltonian. Moreover, we provide an algorithm according to the proof.

Let \(D\) be a finite and simple digraph with vertex set \(V(D)\), and let \(f: V(D) \to \{-1, 1\}\) be a two-valued function. If \(\sum_{x \in N_D^-[v]} f(x) \geq 1\) for each \(v \in V(D)\), where \(N_D^-[v]\) consists of \(v\) and all vertices of \(D\) from which arcs go into \(v\), then \(f\) is a signed dominating function on \(D\). The sum \(\sum_{v \in V(D)} f(v)\) is called the weight of \(f\). The signed domination number, denoted by \(\gamma_S(D)\), of \(D\) is the minimum weight of a signed dominating function on \(D\). In this work, we present different lower bounds on \(\gamma_S(D)\) for general digraphs, show that these bounds are sharp, and give an improvement of a known lower bound obtained by Karami in 2009 [H. Karami, S.M. Sheikholeslami, A. Khodkar, Lower bounds on the signed domination numbers of directed graphs, Discrete Math. 309 (2009), 2567-2570]. Some of our results are extensions of well-known properties of the signed domination number of graphs.

Let \(G\) be a graph of order at least \(2k\) and \(s_1, s_2, \ldots, s_k, t_1, t_2, \ldots, t_k\) be any \(2k\) distinct vertices of \(G\). If there exist \(k\) disjoint paths \(P_1, P_2, \ldots, P_k\) such that \(P_i\) is an \(s_i – t_i\) path for \(1 \leq i \leq k\), we call \(G\) \(k\)-linked. K. Kawarabayashi et al. showed that if \(n \geq 4k – 1\) (\(k \geq 2\)) with \(\sigma_2(G) \geq n + 2k – 3\), then \(G\) is \(k\)-linked. Li et al. showed that if \(G\) is a graph of order \(n \geq 232k\) with \(\sigma_2^*(G) \geq n + 2k – 3\), then \(G\) is \(k\)-linked. For sufficiently large \(n\), it implied the result of K. Kawarabayashi et al. The main purpose of this paper is to lower the bound of \(n\) in the result of Li et al. We show that if \(G\) is a graph of order \(n \geq 111k + 9\) with \(\sigma_2^*(G) \geq n + 2k – 3\), then \(G\) is \(k\)-linked. Thus, we improve the order bound to \(111k + 9\), and when \(n \geq 111k + 9\), it implies the result of \(K\). Kawarabayashi \(et al\).

The classification of all dihedral f-tilings of the Riemannian sphere \(S^2\) ,whose prototiles are two right triangles with at least one isosceles, is given.The combinatorial structure and the symmetry group of each tiling is also achieved.

In [4], the author introduced a new metric on the space \(\text{Mat}_{m \times s}(\mathbb{Z}_q)\), which is the module space of all \(m \times s\) matrices with entries from the finite ring \(\mathbb{Z}_q\) (\(q \geq 2\)), generalizing the classical Lee metric [5] and the array RT-metric [8], and named this metric as GLRTP-metric, which is further renamed as LRTJ-metric (Lee-Rosenbloom-Tsfasman-Jain Metric) in [1]. In this paper, we introduce a complete weight enumerator for codes over \(\text{Mat}_{m \times s}(\mathbb{Z}_q)\) endowed with the LRTJ-metric and obtain a MacWilliams-type identity with respect to this new metric for the complete weight enumerator.

The Zagreb indices and the modified Zagreb indices are important topological indices in mathematical chemistry. In this paper we study the relationship between the modified Zagreb indices and the reformulated modified Zagreb indices with respect to trees.

In this work, we first prove that every prime number \(p \equiv 1 \pmod{4}\) can be written in the form \(p = P^2 – 4Q\)with two positive integers \(P\) and \(Q\). Then, we define the sequence \(B_n(P, Q)\) to be \(B_0 = 2\), \(B_1 = P\), and \(B_n = PB_{n-1} – QB_{n-2}\) for \(n \geq 2\), and derive some algebraic identities on it. Also, we formulate the limit of the cross-ratio for four consecutive numbers \(B_n\), \(B_{n+1}\), \(B_{n+2}\), and \(B_{n+3}\).

An edge set \(F\)is called a restricted edge-cut if \(G – F\) is disconnected and contains no isolated vertices. The minimum cardinality over all restricted edge-cuts is called the restricted edge-connectivity of \(G\), and denoted by \(\lambda'(G)\). A graph \(G\) is called \(\lambda’\)-optimal if \(\lambda'(G) = \xi(G)\), where \(\xi(G) = \min\{d_G(u) + d_G(v) – 2: uv \in E(G)\}\). In this note, we obtain a sufficient condition for a \(k( \geq 3)\)-regular connected graph with two orbits to be \(\lambda’\)-optimal.

Let \(G = (V, E)\) be a connected graph. An edge set \(S \subset E\) is a \(k\)-restricted edge cut if \(G – S\) is disconnected and every component of \(G – S\) has at least \(k\) vertices. The \(k\)-restricted edge connectivity \(\lambda_k(G)\) of \(G\) is the cardinality of a minimum \(k\)-restricted edge cut of \(G\). A graph \(G\) is \(\lambda_k\)-connected if \(k\)-restricted edge cuts exist. A graph \(G\) is called \(\lambda_k\)-optimal if \(\lambda_k(G) = \xi_k(G)\), where \[\xi_k(G) = \min\{|[X, Y]|: X \subseteq V, |X| = k \text{ and } G[X] \text{ is connected}\};\] Here, \(G[X]\) is the subgraph of \(G$\) induced by the vertex subset \(X \subseteq V\), and \(Y = V \setminus X\) is the complement of \(X\); \([X, Y]\) is the set of edges with one end in \(X\) and the other in \(Y\). \(G\) is said to be super-\(\lambda_k\) if each minimum \(k\)-restricted edge cut isolates a connected subgraph of order \(k\). In this paper, we give some sufficient conditions for triangle-free graphs to be super-\(\lambda_3\).

The \(k\)-path-connectivity \(\pi_k(G)\) of a graph \(G\) was introduced by Hager in \(1986\). Recently, Mao investigated the \(3\)-path-connectivity of lexicographic product graphs. Denote by \(G \circ H\) the lexicographic product of two graphs \(G\) and \(H\). In this paper, we prove that \(\pi_4(G \circ H) \geq \lfloor\frac{|V(H)|-2}{3}\rfloor\) for any two connected graphs \(G\) and \(H\). Moreover, the bound is sharp. We also derive an upper bound of \(\pi_4(G \circ H)\), that is, \(\pi_4(G \circ H) \leq 2\pi_4(G)|V(H)|\).

This paper devotes to the investigation of \(3\)-designs admitting the special projective linear group \(\mathrm{PSL}(2, 2^n)\) as an automorphism, and we determine all the possible values of \(n\) in the simple \(3-(2^n + 1, 7, \lambda)\) designs admitting \(\mathrm{PSL}(2,2^n)\) as an automorphism group.

In this note, we characterize graphs with a given small matching number. Specifically, we characterize graphs with minimum degree at least \(2\) and matching number at most \(3\). The characterization when the matching number is at most \(2\) strengthens the result of Lai and Yan’s that characterized the non-supereulerian \(2\)-edge connected graphs with matching at most \(2\). Furthermore, the characterization of graphs with matching number at most \(3\) addresses a conjecture of Lai and Yan in [SuperEulerian graphs and matchings, Applied Mathematics Letters 24 (2011) 1867-1869].

Let \(D(G)\) be the distance matrix of a connected graph \(G\). The distance spectral radius of \(G\) is the largest eigenvalue of \(D(G)\) and has been proposed as a molecular structure descriptor. In this paper, we study the distance spectral radius of graphs with a given independence number. Special attention is paid to graphs with a given independence number and maximal distance spectral radius.

Key distribution is paramount for Wireless Sensor Networks (WSNs). The design of key management schemes is the most important aspect and basic research field in WSNs. A key distribution scheme based on symplectic geometry over fields is proposed, where a 2-dimensional subspace in symplectic geometry represents a node, and all \(2s\)-dimensional non-isotropic subspaces represent the key pool, guaranteeing that every pair of nodes has a shared key, thus improving network connectivity. The performance analysis shows that the scheme has good connectivity and higher resilience to node compromise compared to other key pre-distribution schemes.

For a given graph \(H\), a graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) is said to be potentially \(H\)-graphic if there exists a realization of \(\pi\) containing \(H\) as a subgraph. Let \(K_{ r+1} – C_k\) be the graph obtained from \(K_{ r+1}\) by removing the \(k\) edges of a \(k\)-cycle. In this paper, we first characterize potentially \(A_{ r+1} – C_k\)-graphic sequences (\(3 \leq k \leq r+1\)), analogous to Yin et al.’s characterization [19], using a system of inequalities. Then, we obtain a sufficient and necessary condition for a graphic sequence \(\pi\) to have a realization containing \(K_{r+1} – C_k\) as an induced subgraph.

A graph \(G\) with \(1 \leq n \leq |V(G)| – 2\) is said to be \(n\)-factor-critical if any \(n\) vertices of \(G\) are deleted, then the resultant graph has a perfect matching. An odd graph \(G\) with \(2k \leq |V(G)| – 3\) is said to be near \(k\)-extendable if \(G\) has a \(k\)-matching and any \(k\)-matching of \(G\) can be extended to a near perfect matching of \(G\). Lou and Yu [Australas. J. Combin. 29 (2004) 127-133] showed that any \(5\)-connected planar odd graph is \(3\)-factor-critical. In this paper, as an improvement of Lou and Yu’s result, we prove that any \(4\)-connected planar odd graph is \(3\)-factor-critical and also near \(2\)-extendable. Furthermore, we prove that all \(5\)-connected planar odd graphs are near \(3\)-extendable.

Determining the biplanar crossing number of the graph \(C_n \times C_n \times C_n \times P_n\) was a problem proposed in a paper by Czabarka, Sykora, Székely, and Vito [2]. We find as a corollary to the main theorem of this paper that the biplanar crossing number of the aforementioned graph is zero. This result follows from the decomposition of \(C_n \times C_n \times C_n \times P_m\) into one copy of \(C_{n^2} \times P_{lm},l-2\) copies of \(C_{n^2} \times P_m\), and a copy of \(C_{n^2} \times P_{2m}\).

Let \(A_n\) be the alternating group of degree \(n\) with \(n \geq 5\). Set \(S = \{(1ij), (1ji) \mid 2 \leq i, j \leq n, i \neq j\}\). In this paper, it is shown that the full automorphism group of the Cayley graph \(\mathrm{Cay}(A_n, S)\) is the semi-product \(R(A_n) \rtimes \mathrm{Aut}(A_n, S)\), where \(R(A_n)\) is the right regular representation of \(A_n\) and \(\mathrm{Aut}(A_n, S) = \{\phi \in \mathrm{Aut}(A_n) \mid S^\phi = S\} \cong \mathrm{S_{n-1}}\).

Topological indices of graphs, and trees in particular, have been vigorously studied in the past decade due to their many applications in different fields. Among such indices, the number of subtrees (BC-subtrees), along with their variations, have received much attention. In this paper, we provide some new evaluation results related to these two indices on specific structures, such as generalized Bethe trees, Bethe trees, and dendrimers, which are of practical interest. Using generating functions, we also examine the asymptotic behavior of subtree (resp. BC-subtree) density of dendrimers.

For an integer \(k \geq 0\), a graphical property \(P\) is said to be \(k\)-stable if whenever \(G + uv\) has property \(P\) and \(d_G(u) + d_G(v) \geq k\), where \(uv \notin E(G)\), then \(G\) itself has property \(P\). In this note, we present spectral sufficient conditions for several stable properties of a graph.

Let \(G\) be a connected graph. The degree resistance distance of \(G\) is defined as \(D_R(G) = \sum\limits_{\{u,v\} \in V(G)} (d(u) + d(v))r(u,v)\), where \(d(u)\) (and \(d(v)\)) is the degree of the vertex \(u\) (and \(v\)), and \(r(u,v)\) is the resistance distance between vertices \(u\) and \(v\). A fully loaded unicyclic graph is a unicyclic graph with the property that there is no vertex with degree less than \(3\) in its unique cycle. In this paper, we determine the minimum and maximum degree resistance distance among all fully loaded unicyclic graphs with \(n\) vertices, and characterize the extremal graphs.

The cyclic edge-connectivity of a cyclically separable graph \(G\), denoted by \(c\lambda(G)\), is the minimum cardinality of all edge subsets \(F\) such that \(G – F\) is disconnected and at least two of its components contain cycles. Since \(c\lambda(G) \leq \zeta(G)\), where \(\zeta(G) = \min\{w(A) \mid A \text{ induces a shortest cycle in } G\}\), for any cyclically separable graph \(G\), a cyclically separable graph \(G\) is said to be cyclically optimal if \(c\lambda(G) = \zeta(G)\). The mixed Cayley graph is a kind of semi-regular graph. The cyclic edge-connectivity is a widely studied parameter, which can be used to measure the reliability of a network. Because previous work studied cyclically optimal mixed Cayley graphs with girth \(g \geq 5\), this paper focuses on mixed Cayley graphs with girth \(g < 5\) and gives some sufficient and necessary conditions for these graphs to be cyclically optimal.