Given a set of vertices \(S = \{v_1, v_2, \ldots, v_k\}\) of a connected graph \(G\), the metric representation of a vertex \(v\) of \(G\) with respect to \(S\) is the vector \(r(v|S) = (d(v, v_1), d(v, v_2), \ldots, d(v, v_k))\), where \(d(v, v_i)\), \(i \in \{1, \ldots, k\}\), denotes the distance between \(v\) and \(v_i\). \(S\) is a resolving set of \(G\) if for every pair of distinct vertices \(u, v\) of \(G\), \(r(u|S) \neq r(v|S)\). The metric dimension \(\dim(G)\) of \(G\) is the minimum cardinality of any resolving set of \(G\). Given an ordered partition \(\Pi = \{P_1, P_2, \ldots, P_t\}\) of vertices of a connected graph \(G\), the partition representation of a vertex \(v\) of \(G\), with respect to the partition \(\Pi\), is the vector \(r(v|\Pi) = (d(v, P_1), d(v, P_2), \ldots, d(v, P_t))\), where \(d(v, P_i)\), \(1 \leq i \leq t\), represents the distance between the vertex \(v\) and the set \(P_i\), that is \(d(v, P_i) = \min_{u \in P_i} \{d(v, u)\}\). \(\Pi\) is a resolving partition for \(G\) if for every pair of distinct vertices \(u, v\) of \(G\), \(r(u|\Pi) \neq r(v|\Pi)\). The partition dimension \(\mathrm{pd}(G)\) of \(G\) is the minimum number of sets in any resolving partition for \(G\). Let \(G\) and \(H\) be two graphs of order \(n\) and \(m\), respectively. The corona product \(G \odot H\) is defined as the graph obtained from \(G\) and \(H\) by taking one copy of \(G\) and \(n\) copies of \(H\) and then joining, by an edge, all the vertices from the \(i\)-th copy of \(H\) with the \(i\)-th vertex of \(G\). Here, we study the relationship between \(\mathrm{pd}(G \odot H)\) and several parameters of the graphs \(G \odot H\), \(G\), and \(H\), including \(\dim(G \odot H)\), \(\mathrm{pd}(G)\), and \(\mathrm{pd}(H)\).

We study: combination and permutation graphs. We introduce some familes to be: combination graphs and permutation graphs.

An \(L(2, 1)\)-labeling of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to the set of all nonnegative integers such that \(|f(x) – f(y)| \geq 2\) if \(d(x, y) = 1\) and \(|f(x) – f(y)| \geq 1\) if \(d(x, y) = 2\), where \(d(x, y)\) denotes the distance between \(x\) and \(y\) in \(G\). The \(L(2, 1)\)-labeling number, \(\lambda(G)\), of \(G\) is the smallest number \(k\) such that \(G\) has an \(L(2, 1)\)-labeling \(f\) with \(\max\{f(v) : v \in V(G)\} = k\). In this paper, we present a new characterization on \(d\)-disk graphs for \(d > 1\). As an application, we give upper bounds on the \(L(2, 1)\)-labeling number for these classes of graphs.

The Randić index \(R(G)\) of a graph \(G\) is the sum of the weights \((d_u d_v)^{-\frac{1}{2}}\) over all edges \(uv\) of \(G\), where \(d_u\) denotes the degree of the vertex \(u\). In this paper, we determine the first ten, eight, and six largest values for the Randić indices among all trees, unicyclic graphs, and bicyclic graphs of order \(n \geq 11\), respectively. These extend the results of Du and Zhou [On Randić indices of trees, unicyclic graphs, and bicyclic graphs, International Journal of Quantum Chemistry, 111 (2011), 2760–2770].

A paired-dominating set of a graph \(G\) is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number is the minimum cardinality of a paired-dominating set of \(G\). In this paper, we investigate the paired-domination number in claw-free graphs with minimum degree at least four. We show that a connected claw-free graph \(G\) with minimum degree at least four has paired-domination number at most \(\frac{4}{7}\) its order.

Given a set of vertices \(S = \{v_1, v_2, \ldots, v_k\}\) of a connected graph \(G\), the metric representation of a vertex \(v\) of \(G\) with respect to \(S\) is the vector \(r(v|S) = (d(v, v_1), d(v, v_2), \ldots, d(v, v_k))\), where \(d(v, v_i)\), \(i \in \{1, \ldots, k\}\), denotes the distance between \(v\) and \(v_i\). \(S\) is a resolving set of \(G\) if for every pair of distinct vertices \(u, v\) of \(G\), \(r(u|S) \neq r(v|S)\). The metric dimension \(\dim(G)\) of \(G\) is the minimum cardinality of any resolving set of \(G\). Given an ordered partition \(\Pi = \{P_1, P_2, \ldots, P_t\}\) of vertices of a connected graph \(G\), the partition representation of a vertex \(v\) of \(G\), with respect to the partition \(\Pi\), is the vector \(r(v|\Pi) = (d(v, P_1), d(v, P_2), \ldots, d(v, P_t))\), where \(d(v, P_i)\), \(1 \leq i \leq t\), represents the distance between the vertex \(v\) and the set \(P_i\), that is \(d(v, P_i) = \min_{u \in P_i} \{d(v, u)\}\). \(\Pi\) is a resolving partition for \(G\) if for every pair of distinct vertices \(u, v\) of \(G\), \(r(u|\Pi) \neq r(v|\Pi)\). The partition dimension \(\mathrm{pd}(G)\) of \(G\) is the minimum number of sets in any resolving partition for \(G\). Let \(G\) and \(H\) be two graphs of order \(n\) and \(m\), respectively. The corona product \(G \odot H\) is defined as the graph obtained from \(G\) and \(H\) by taking one copy of \(G\) and \(n\) copies of \(H\) and then joining, by an edge, all the vertices from the \(i\)-th copy of \(H\) with the \(i\)-th vertex of \(G\). Here, we study the relationship between \(\mathrm{pd}(G \odot H)\) and several parameters of the graphs \(G \odot H\), \(G\), and \(H\), including \(\dim(G \odot H)\), \(\mathrm{pd}(G)\), and \(\mathrm{pd}(H)\).

A bridge graph is a special one of those graphs with more than one cut-edge. In this paper, we compute Wiener, hyper-Wiener, \(PI\) and vertex \(PI\) indices of graphs with more than one cut-edge, which generalize results in [12, 13, 14].

For an ordered set \(W = \{w_1, w_2, \ldots, w_k\}\) of vertices and a vertex \(v\) in a connected graph \(G\), the ordered \(k\)-vector \(r(v|W) := (d(v, w_1), d(v, w_2), \ldots, d(v, w_k))\) is called the (metric) representation of \(v\) with respect to \(W\), where \(d(x, y)\) is the distance between the vertices \(x\) and \(y\). The set \(W\) is called a resolving set for \(G\) if distinct vertices of \(G\) have distinct representations with respect to \(W\). A minimum resolving set for \(G\) is a basis of \(G\) and its cardinality is the metric dimension of \(G\). The resolving number of a connected graph \(G\) is the minimum \(k\) such that every \(k\)-set of vertices of \(G\) is a resolving set. A connected graph \(G\) is called randomly \(k\)-dimensional if each \(k\)-set of vertices of \(G\) is a basis. In this paper, along with some properties of randomly \(k\)-dimensional graphs, we prove that a connected graph \(G\) with at least two vertices is randomly \(k\)-dimensional if and only if \(G\) is a complete graph \(K_{k+1}\) or an odd cycle.

We say that \(G\) is nearly claw-free if for every \(v \in A\), the set of centers of claws of \(G\), there exist two vertices \(x, y \in N(v)\) such that \(x, y \notin A\) and \(N_G(v) \subseteq N_G(x) \cup N_G(y) \cup \{x, y\}\). A graph \(G\) is triangularly connected if for every pair of edges \(e_1, e_2 \in E(G)\), \(G\) has a sequence of \(3\)-cycles \(C_1, C_2, \ldots, C_r\) such that \(e_1 \in C_1, e_2 \in C_l\) and \(E(C_i) \cap E(C_{i+1}) \neq \emptyset\) for \(1 \leq i \leq l-1\). In this paper, we will show that (i) every triangularly connected \(K_{1,4}\)-free nearly claw-free graph on at least three vertices is fully cycle extendable if the clique number of the subgraph induced by the set of centers of claws of \(G\) is at most \(2\), and (ii) every \(4\)-connected line graph of a nearly claw-free graph is hamiltonian connected.

In this paper, we will find a combinatorial formula that relates the power of a \(k\)-Fibonacci number, \(F_{k,n}^p\), to the number \(F_{k,an}\). From this formula, and if \(p\) is odd, we will find a new formula that allows expressing the \(k\)-Fibonacci number \(F_{k,(2r+1)n}\) as a combination of odd powers of \(F_{k,n}\). If \(p\) is even, the formula is similar but for the even \(k\)-Lucas numbers \(L_{k,2rn}\).

The resistance distance between two vertices of a connected graph \(G\) is defined as the effective resistance between them in the corresponding electrical network constructed from \(G\) by replacing each edge of \(G\) with a unit resistor. The Kirchhoff index \(Kf(G)\) is the sum of resistance distances between all pairs of vertices of the graph \(G\). In this paper, we determine the tricyclic graphs with the smallest and the second smallest Kirchhoff indices.

The basis number of a graph \(G\) is defined to be the least non-negative integer \(d\) such that there is a basis \(\mathcal{B}\) of the cycle space of \(G\) such that each edge of \(G\) is contained in at most \(d\) members of \(\mathcal{B}\). In this paper, we determine the basis number of the wreath product of different ladders.

The \(Co-PI\) index have been introduced by Hasani et al. recently. In this paper, we present a new version for the \(Co-PI\) index, and the Cartesian product, Corona product and join of graphs under this new index are computed.

In this paper we give upper bounds of the number of edges in four types of labeled graphs of known orders.

In this paper, some lattices generated by the orbits of the subspaces under finite classical groups are considered. the characteristic polynomials of these lattices are obtained by using the effective approach by Aigner in \([2]\) , and their expressions are also determined.

In this paper, we study \(CT\)-burst array error \([6]\) detection and correction in row-cyclic array codes \([8]\).

In this work, we define a new integer sequence related to Fibonacci and Pell sequences with four parameters and then derived some algebraic identities on it including, the sum of first non-zero terms, recurrence relations, rank of its terms, powers of companion matrix and the limit of cross-ratio of four consecutive terms of it.

The hexagonal system considered here, denoted by \({E}_n^2\), is formed by \(3n\) (\(n \geq 2\)) hexagons shown in Fig. 2(a). In this paper, we give the explicit expression of the characteristic polynomial \(\Phi_A({E}_n^2, x)\). Subsequently, we obtain the multiplicity of eigenvalues \(+1\), the spectral radius, and the nullity of \({E}_n^2\). Furthermore, the energy, Estrada index, and the number of Kekulé structures of \({E}_n^2\) are determined.

The frequency assignment problem originated in researching mobile communication networks. A proper total coloring of a graph \(G\) is a coloring of both edges and vertices of \(G\) such that no two adjacent or incident elements receive the same color. As known, the vertex distinguishing total coloring is one of the suitable tools for investigating the frequency assignment problem. We introduce a new graph total coloring, called \((4)\)-adjacent vertex distinguishing total coloring (\((4)\)-AVDTC), in this paper. Our coloring contains the adjacent vertex distinguishing total coloring. The minimum number of colors required for every \((4)\)-AVDTC of \(G\) is called the \((4)\)-AVDTC chromatic number of \(G\). We will show that using at most \(\Delta(G) + 4\) colors can achieve at least \(4\) different adjacent vertex distinguishing actions for some communication networks \(G\). The exact \((4)\)-AVDTC chromatic numbers of several classes of graphs are determined here and a problem is presented.

Let \(R\) be a commutative ring with identity and \(T(\Gamma(R))\) its total graph. The subject of this article is the investigation of the properties of the corresponding line graph \(L(T(\Gamma(R)))\). The classification of all commutative rings whose line graphs are planar or toroidal is given. It is shown that for every integer \(g \geq 0\) there are only finitely many commutative rings such that \(\gamma(L(T(\Gamma(R)))) = g\).

Sparse anti-magic squares are useful in constructing vertex-magic labelings for bipartite graphs. An \(n \times 7\) array based on \(\{0, 1, \ldots, nd\}\) is called a sparse anti-magic square of order \(n\) with density \(d\) (\(d < n\)), denoted by SAMS\((n, d)\), if its row-sums, column-sums, and two main diagonal sums constitute a set of \(2n + 2\) consecutive integers. A SAMS\((n, d)\) is called regular if there are \(d\) positive entries in each row, each column, and each main diagonal. In this paper, some constructions of regular sparse anti-magic squares are provided and it is shown that there exists a regular SAMS\((n, d-1)\) if and only if \(n \geq 4\).

In this paper, we perform a further investigation for the \(q\)-analogues of the classical Bernoulli numbers and polynomials. By applying summation transform techniques, we establish some new recurrence relations for these type numbers and polynomials. We also present some illustrative special cases as well as immediate consequences of the main results.

The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as \[t(G) = \min\left\{\frac{|S|}{w(G – S)} \mid S \subset V(G), w(G – S) \geq 2\right\}\] and the toughness of a complete graph is \(\infty\), where \(w(G – S)\) is the number of connected components of \(G – S\). In this paper, we give the sharp upper and lower bounds for the Kronecker product of a complete graph and a tree. Moreover, we determine the toughness of the Kronecker product of a complete graph and a star, a path, respectively.

For a vertex \(v\) of a graph \(G\), Zhu, Li, and Deng introduced the concept of implicit degree \(id(v)\), according to the degrees of its neighbors and the vertices at distance \(2\) with \(v\) in \(G\). For \(S \subset V(G)\), let \(i\Delta_2(S)\) denote the maximum value of the implicit degree sum of two vertices of \(S\). In this paper, we will prove the following result: Let \(G\) be a \(2\)-connected graph on \(n \geq 3\) vertices. If \(i\Delta_2(S) \geq d\) for each independent set \(S\) of order \(\kappa(G) + 1\), then \(G\) has a cycle of length at least \(\min\{d, n\}\). This result generalizes one result of Yamashita [T. Yamashita, On degree sum conditions for long cycles and cycles through specified vertices, Discrete Math., \(308 (2008) 6584-6587]\).

For a given graph \(G = (V, E)\), by \(f(v)\), we denote the sum of the color on the vertex \(v\) and the colors on the edges incident with \(v\). A proper \(k\)-total coloring \(\phi\) of a graph \(G\) is called a neighbor sum distinguishing \(k\)-total coloring if \(f(u) \neq f(v)\) for each edge \(uv \in E(G)\). The smallest number \(k\) in such a coloring of \(G\) is the neighbor sum distinguishing total chromatic number, denoted by \(\chi”_{\sum}(G)\). The maximum average degree of \(G\) is the maximum of the average degree of its non-empty subgraphs, which is denoted by \(\mathrm{mad}(G)\). In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that if \(G\) is a graph with \(\Delta(G) \geq 6\) and \(\mathrm{mad}(G) < \frac{18}{5}\), then \(\chi''_{\sum}(G) \leq \Delta(G) + 2\). This bound is sharp.

A two-character set is a set of points of a finite projective space that has two intersection numbers with respect to hyperplanes. Two-character sets are related to strongly regular graphs and two-weight codes. In the literature, there are plenty of constructions for (non-trivial) two-character sets by considering suitable subsets of quadrics and Hermitian varieties. Such constructions exist for the quadrics \(Q^{+}(2n-1,4) \subseteq PG(2n-1,q)\), \(Q^{-}(2n+1,4) \subseteq PG(2n+1,q)\) and the Hermitian varieties \(H(2n-1,q^{2}) \subseteq PG(2n-1,q^{2})\), \(H(2n,q^{2}) \subseteq PG(2n,q^{2})\). In this note, we show that every two-character set of \(PG(2n,q)\) that is contained in a given nonsingular parabolic quadric \(Q(2n,q) \subseteq PG(2n,q)\) is a subspace of \(PG(2n,q)\). This offers some explanation for the absence of the parabolic quadrics in the above-mentioned constructions.

Using the companion matrices, we get more identities and Hessenberg matrices about Fibonacci and Tribonacci numbers.
By Fibonacci and Tribonacci numbers we can evaluate the determinants and permanents of some special Hessenberg matrices.

Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). A function \(f: E(G) \rightarrow \{-1, 1\}\) is said to be a signed star dominating function of \(G\) if \(\sum_{e \in E_G(v)} f(e) \geq 1\) for every \(v \in V(G)\), where \(E_G(v) = \{uv \in E(G) | u \in V(G)\}\). The minimum of the values of \(\sum_{e \in E(G)} f(e)\), taken over all signed dominating functions \(f\) on \(G\), is called the signed star domination number of \(G\) and is denoted by \(\gamma_{SS}(G)\). In this paper, we prove that \(frac{n}{2}\leq \gamma_{SS}(T) \leq n-1\) for every tree \(T\) of order \(n\), and characterize all trees on \(n\) vertices with signed star domination number \(\frac{n}{2}\), \(\frac{n+1}{2}\), \(n-1\), or \(n-3\).

The concept of rainbow connection was introduced by Chartrand et al. in 2008. The rainbow connection number, \(rc(G)\), of a connected graph \(G = (V, E)\) is the minimum number of colors needed to color the edges of \(E\), so that each pair of vertices in \(V\) is connected by at least one path in which no two edges are assigned the same color. The rainbow vertex-connection number, \(rvc(G)\), is the vertex version of this problem. In this paper, we introduce mixed integer programming models for both versions of the problem. We show the validity of the proposed models and test their efficiency using a nonlinear programming solver.

A graph of order \(n\) is \(p\)-factor-critical, where \(p\) is an integer with the same parity as \(n\), if the removal of any set of \(p\) vertices results in a graph with a perfect matching. It is well known that a connected vertex-transitive graph is \(1\)-factor-critical if it has odd order and is \(2\)-factor-critical or elementary bipartite if it has even order. In this paper, we show that a connected non-bipartite vertex-transitive graph \(G\) with degree \(k \geq 6\) is \(p\)-factor-critical, where \(p\) is a positive integer less than \(k\) with the same parity as its order, if its girth is not less than the bigger one between \(6\) and \( \frac{k(p-1)+8}{2(k-2)}\).

In this paper, the completely regular endomorphisms of a split graph are investigated. We give necessary and sufficient conditions the completely regular endomorphisms of a split graph form a monoid.

In this paper, we interpret a generalized basic series as the generating function of two different combinatorial objects, viz., a restricted \(n\)-colour partition function, which we call a two-colour partition function, and a weighted lattice path function. This leads to infinitely many combinatorial identities. Our main result has the potential of yielding many Rogers-Ramanujan-MacMahon type combinatorial identities. This is illustrated by an example.

Let \(u\) and \(v\) be two vertices in a graph \(G\). We say vertex \(u\) dominates vertex \(v\) if \(N(v) \subseteq N(u) \cup \{u\}\). If \(u\) dominates \(v\) or \(v\) dominates \(u\), then \(u\) and \(v\) are comparable. The Dilworth number of a graph \(G\), denoted \(\text{Dil}(G)\), is the largest number of pairwise incomparable vertices in the graph \(G\). A graph \(G\) is called \(\{H_1, H_2, \ldots, H_k\}\)-free if \(G\) contains no induced subgraph isomorphic to any \(H_i\), \(1 \leq i \leq k\). A graph \(G\) is called an \(L_1\)-graph if, for each triple of vertices \(u\), \(v\), and \(w\) with \(d(u,v) = 2\) and \(w \in N(u) \cap N(v)\), \(d(u)+d(v) \geq |N(u) \cup N(v) \cup N(w)| – 1\). Let \(G\) be a \(k\) (\(k \geq 2\))-connected \(L_2\)-graph. If \(G\) is \(\{K_{1,5}, K_{1,5+e}\}\)-free and \(\text{Dil}(G) \leq 2k-1\), then \(G\) is Hamiltonian or \(G \in \mathcal{F}\), where \(K_{1,5}+e\) is a graph obtained by joining a pair of nonadjacent vertices in \(K_{s,s}\) and \(\mathcal{F} = \{G : K_{p,p-1} \subseteq G \subseteq K_{p} \vee (p+1)K_1, 2 \leq p \leq 3\}\), where \(\vee\) denotes the join operation of two graphs.

For a simple digraph \(D\) with \(n\) vertices, the energy of \(D\) is defined as \(E(D) = \sum_{i=1}^{n} |\Re(z_i)|\), where \(z_1, z_2, \ldots, z_n\) are the eigenvalues of \(D\). This paper first gives an improved lower bound on the spectral radius of \(D\), which is used to obtain some upper bounds for the energy \(E(D)\). These results improve and generalize some known results on upper bounds of the energy of digraphs.

A vertex \(v \in V(G)\) is said to be a self vertex switching of \(G\) if \(G\) is isomorphic to \(G^v\), where \(G^v\) is the graph obtained from \(G\) by deleting all edges of \(G\) incident to \(v\) and adding all edges incident to \(v\) which are not in \(G\). The set of all self vertex switchings of \(G\) is denoted by \({SS_1}(G)\) and its cardinality by \(ss_1(G)\). In [6], the number \(ss_1(G)\) is calculated for the graphs cycle, path, regular graph, wheel, Euler graph, complete graph, and complete bipartite graphs. In this paper, for a vertex \(v\) of a graph \(G\), the graph \(G^v\) is characterized for tree, star, and forest with a given number of components. Using this, we characterize trees and forests, each with a self vertex switching.

Permutation tableaux were introduced in the study of totally positive Grassmannian cells, and are connected with the steady state of asymmetric exclusion process, which is an important model from statistical mechanics. In this paper, we firstly establish a shape-preserving involution on the set of permutation tableaux of length \(n\), which directly shows that the number of permutation tableaux of length \(n\) with \(k\) essential 1’s equals the number of permutation tableaux of length \(n\) with \(n-k\) unrestricted rows. In addition, we introduce three combinatorial structures, called free permutation tableaux, restricted set partitions, and labeled Dyck paths. We discuss the properties of their internal structures and present the correspondence between the set of free permutation tableaux of length \(n\) and the set of restricted set partitions of \(\{1,2,\ldots,n\}\), and we also give a bijection between the set of restricted set partitions of \(\{1,2,\ldots,n\}\) and the set of labeled Dyck paths of length \(2n\). Finally, we make a generalization of the latter bijection.

Let \(G = (V, E)\) be a connected multigraph with order \(n\). \(\delta(G)\) and \(\lambda(G)\) are the minimum degree and edge connectivity, respectively. The multigraph \(G\) is called maximally edge-connected if \(\lambda(G) = \delta(G)\) and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. A sequence \(D = (d_1, d_2, \ldots, d_n)\) with \(d_1 \geq d_2 \geq \ldots \geq d_n\) is called a multigraphic sequence if there is a multigraph with vertices \(v_1, v_2, \ldots, v_n\) such that \(d(v_i) = d_i\) for each \(i = 1, 2, \ldots, n\). The multigraphic sequence \(D\) is super edge-connected if there exists a super edge-connected multigraph \(G\) with degree sequence \(D\). In this paper, we present that a multigraphic sequence \(D\) with \(d_n = 1\) is super edge-connected if and only if \(\sum\limits_{i=1}^{n} d_i \geq 2n\) and give a sufficient and necessary condition for a multigraphic sequence \(D\) with \(d_n = 2\) to be super edge-connected. Moreover, we show that a multigraphic sequence \(D\) with \(d_n \geq 3\) is always super edge-connected.