A family \(\mathcal{G}\) of connected graphs is said to be a family with constant metric dimension if \(\dim(G)\) does not depend upon the choice of \(G\) in \(\mathcal{G}\). In this paper, we study the metric dimension of some plane graphs obtained from convex polytopes by attaching a pendant edge to each vertex of the outer cycle in a plane representation of these convex polytopes. We prove that the metric dimension of these plane graphs is constant and only three vertices, appropriately chosen, suffice to resolve all vertices of these classes of graphs. It is natural to ask for the characterization of graphs \(G\) that are plane representations of convex polytopes having the property that \(\dim(G) = \dim(G’)\), where \(G’\) is obtained from \(G\) by attaching a pendant edge to each vertex of the outer cycle of \(G\).

It is well known that the properties about the power sequences of different classes of sign pattern matrices may be very different. In this paper, we consider the base of primitive nonpowerful zero-symmetric square sign pattern matrices without nonzero diagonal entry. The base set is shown to be \(\{2, 3, \ldots, 2n – 1\}\); the extremal sign pattern matrices with base \(2n – 1\) are characterized. As well, for the sign patterns with order \(3\), the sign patterns with bases \(3\), \(4\), \(5\) are characterized, respectively.

In this note, we study clique number, chromatic number,domination number and independence number of the intersection graph of subspaces of a finite dimensional vector space over a finite field.

A vertex-colored graph \(G\) is rainbow connected, if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex connection number of a connected graph \(G\), denoted \(\mathrm{rvc}(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow vertex connected. In this paper, we show that \(\mathrm{rvc}(G) \leq k\), if \(|E(G)| \geq \binom{n-k}{2} + k\), for \(k = 2, 3, n-4, n-5, n-6\). These bounds are sharp.

In order to find more sufficient conditions for the existence of hamiltonian cycles of graphs, Zhu, Li, and Deng proposed the definition of implicit degree of a vertex. In this paper, we consider the relationship between implicit degrees of vertices and the hamiltonicity of graphs, and obtain that: If the implicit degree sum for each pair of nonadjacent vertices of an induced claw or an induced modified claw in a \(2\)-connected graph \(G\) is more than or equal to \(|V(G)| – 1\), then \(G\) is hamiltonian with some exceptions. This extends a previous result of Cai et al. [J. Cai, H. Li and W. Ning, An implicit degree condition for hamiltonian cycles, Ars Combin. \(108 (2013) 365-378.]\) on the existence of hamiltonian cycles.

The general vertex-distinguishing total chromatic number of a graph \(G\) is the minimum integer \(k\), for which the vertices and edges of \(G\) are colored using \(k\) colors such that there are no two vertices possessing the same color-set, where a color-set of a vertex is a set of colors of the vertex and its incident edges. In this paper, we discuss the general vertex-distinguishing total chromatic number of complete bipartite graphs \(K_{m,n}\), and obtain the exact value of this number for some cases in terms of \(m\) and \(n\). Particularly, we give the bounds of this number for \(K_{n,n}\).

In this paper we characterize the unique graph whose algebraic connectivity is minimum among all connected graphs with given order and fixed matching number or edge covering number, and present two lower bounds for the algebraic connectivity in terms of the matching number or edge covering number.

Let \(G = (V, E)\) be a graph and \(\phi: V \cup E \to \{1, 2, \ldots, \alpha\}\) be a proper \(\alpha\)-total coloring of \(G\). Let \(f(v)\) denote the sum of the color on vertex \(v\) and the colors on the edges incident with \(v\). A neighbor sum distinguishing \(\alpha\)-total coloring of \(G\) is a proper \(\alpha\)-total coloring of \(G\) such that for each edge \(uv \in E(G)\), \(f(u) \neq f(v)\). Pileeniak and Woźniak first introduced this coloring and conjectured that such coloring exists for any simple graph \(G\) with maximum degree \(\Delta(G)\) if \(\alpha \geq \Delta(G) + 3\). The maximum average degree of \(G\) is the maximum of the average degree of its non-empty subgraphs, which is denoted by \(mad(G)\). In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that this conjecture holds for graphs with larger maximum average degree in their list versions. More precisely, we prove that if \(G\) is a graph with \(\Delta(G) \geq 11\) and \(mad(G) < 5\), then \(ch''_{\Sigma}(G) \leq \Delta(G) + 3\), where \(ch''_{\Sigma}(G)\) is the neighbor sum distinguishing total choosability of \(G\).

Let \(\mathcal{K}\) be a family of sets in \(\mathbb{R}^d\) and let \(k\) be a fixed natural number. Assume that every countable subfamily of \(K\) has an intersection expressible as a union of \(k\) starshaped sets, each having a \(d\)-dimensional kernel. Then \(S = \cap \{K : K \in \mathcal{K}\}\) is nonempty and is expressible as a union of \(k\) such starshaped sets.

If members of \(K\) are compact and every finite subfamily of \(\mathcal{K}\) has as its intersection a union of \(k\) starshaped sets, then \(S\) again is a union of \(k\) starshaped sets. An analogous result holds for unions of \(k\) convex sets. Finally, dual results hold for unions of subfamilies of \(\mathcal{K}\).

We give relationships among the binomial coefficients, the Bemoulli numbers and the Stirling numbers, These relations are derived from the translation formulae in the linear discrete systems in Shin-Naito \([8]\).

In this paper, we give the continued fraction expansions of the ordinary generating functions of the derangement polynomials of types \(A\) and \(B\) in a unified manner. Our proof is based on their exponential generating functions and the theory of exponential Riordan arrays.

A graph is called End-regular if its endomorphism monoid is regular. Which graphs are End-regular? This is an open question and difficult to obtain a general answer. In the present paper, we investigate the End-regularity of graphs obtained by adding or deleting vertices from End-regular graphs. As an application, we show that the non-commuting graphs of \(AC\)-groups are End-regular.

In this paper, we study some identities of Barnes-type Genocchi polynomials. We derive those identities by using the fermionic \(p\)-adic integral on \(\mathbb{Z}_p\).
In \([13]\), D.S. Kim and T. Kim established some identities of higher-order Bernoulli and Euler polynomials arising from Bernoulli and Euler basis, respectively. Using the idea developed in \([13]\), we study various identities of special polynomials arising from Barnes-type Genocchi basis.

Suppose that the vertex set of a graph \(G\) is \(V(G) = \{v_1, \ldots, v_n\}\). Then we denote by \({Tr_G}(v_i)\) the sum of distances between \(v_i\) and all other vertices of \(G\). Let \({Tr}(G)\) be the \(n \times n\) diagonal matrix with its \((i,i)\)-entry equal to \({Tr_G}(v_i)\) and \(D(G)\) be the distance matrix of \(G\). Then \(L_p(G) = {Tr}(G) – D(G)\) is the distance Laplacian matrix of \(G\). The largest eigenvalues of \(D(G)\) and \(L_p(G)\) are called distance spectral and distance Laplacian spectral radius of \(G\), respectively. In this paper, we describe the unique graph with maximum distance and distance Laplacian spectral radius among all connected graphs of order \(n\) with given cut edges.

A radio labeling of a connected graph \(G\) of diameter \(d\) is a mapping \(f: V(G) \to \{0, 1, 2, \ldots\}\) such that \(d(u, v) + |f(u) – f(v)| \geq d + 1\) for each pair of distinct vertices \(u\) and \(v\) of \(G\), where \(d(u, v)\) is the distance between \(u\) and \(v\). The value \(rn(f)\) of a radio labeling \(f\) is the maximum label assigned by \(f\) to a vertex of \(G\). The radio number \(rn(G)\) of \(G\) is the minimum value of \(rn(f)\) taken over all radio labelings \(f\) of \(G\). A caterpillar \(C_{m,t}\) is a special tree that consists of a path \(x_1x_2 \ldots x_m\) (\(m \geq 3\)), with some pendant vertices adjacent to the inner vertices \(x_2, x_3, \ldots, x_{m-1}\). If \(d(x_i) = t\) (the degree of \(x_i\)) for \(i = 2, 3, \ldots, m-1\), then the caterpillar is called standard. In this paper, we determine the exact value of the radio number of \(C_{m,t}\) for all integers \(m \geq 4\) and \(t \geq 2\), and explicitly construct an optimal radio labeling. Our results show that the radio number and the construction of optimal radio labeling of paths are special cases of \(C_{m,t}\) with \(t = 2\).

Graph theory, with its diverse applications in theoretical computer science and in natural sciences (chemistry, biology), is becoming an important component of mathematics. Recently, the concepts of new Zagreb eccentricity indices were introduced. These indices were defined for any graph \(G\), as follows: \(M_1^*(G) = \sum_{e_{uv} \in E(G)} [\varepsilon_G(u) + \varepsilon_G(v)]\), \(M_1^{**}(G) = \sum_{v \in V(G)} [\varepsilon_G(v)]^2\), and \(M_2^*(G) = \sum_{e_{uv} \in E(G)} |\varepsilon_G(u) – \varepsilon_G(v)|\), where \(\varepsilon_G(u)\) is the eccentricity value of vertex \(u\) in the graph \(G\). In this paper, new Zagreb eccentricity indices \(M_1^*(G)\), \(M_1^{**}(G)\), and \(M_2^*(G)\) of cycles related graphs, namely gear, friendship, and corona graphs, are determined. Then, a programming code finding values of new Zagreb indices of any graph is offered.

Bizley [J. Inst. Actuar. 80 (1954), 55-62] studied a generalization of Dyck paths from \((0,0)\) to \((pn, gn)\) (\(\gcd(p,q) = 1\)), which never go below the line \(py = qx\) and are made of steps in \(\{(0, 1), (1,0)\}\), called the step set, and calculated the number of such paths. In this paper, we mainly generalize Bizley’s results to an arbitrary step set \(S\). We call these paths \(S\)-\((p,q)\)-Dyck paths, and give explicit enumeration formulas for such paths. In addition, we provide a proof of these formulas using the method presented in Gessel [J. Combin. Theory Ser. A 28 (1980), no. 3, 321-337]. As applications, we calculate some examples which generalize the classical Schröder and Motzkin numbers.

A \(2\)-rainbow dominating function of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to the set of all subsets of the set \(\{1,2\}\) such that for any vertex \(v \in V(G)\) with \(f(v) = \emptyset\) the condition \(\bigcup_{u \in N(v)} f(u) = \{1,2\}\) is fulfilled, where \(N(v)\) is the open neighborhood of \(v\). A rainbow dominating function \(f\) is said to be a rainbow restrained domination function if the induced subgraph of \(G\) by the vertices with label \(\emptyset\) has no isolated vertex. The weight of a rainbow restrained dominating function is the value \(w(f) = \sum_{v \in V(G)} |f(v)|\). The minimum weight of a rainbow restrained dominating function of \(G\) is called the rainbow restrained domination number of \(G\). In this paper, we continue the study of the rainbow restrained domination number. First, we classify all graphs \(G\) of order \(n\) whose rainbow restrained domination number is \(n-1\). Then, we establish an upper bound on the rainbow restrained domination number of trees.

The entire chromatic number \(\chi_c(G)\) of a plane graph \(G(V, E, F)\) is the minimum number of colors such that any two distinct adjacent or incident elements receive different colors in \(V(G) \cup E(G) \cup F(G)\). A plane graph \(G\) is called a \(1\)-tree if there exists a vertex \(u \in V(G)\) such that \(G – u\) is a forest. In this paper, it is proved that if \(G\) is a \(2\)-connected \(1\)-tree with \(\Delta(G) \geq 6\), then the entire chromatic number of \(G\) is \(\Delta(G) + 1\), where \(\Delta(G)\) is the maximum degree of \(G\).

In this paper, we compute various finite sums that alternate according to \((-1)^{\binom{n}{k}}\) involving the generalized Fibonacci and Lucas numbers for \(k = 3, 4, 5\) and even \(k\) of the form \(2^m\) with \(m \geq 1\).

In this paper, we introduce a special \((k_1A_1, k_2A_2, k_3A_3)\)-edge colouring of a graph. We shall show that for special graphs and special values of \(k_i\), \(i = 1, 2, 3\), the number of such colourings generalizes the well-known Pell numbers. Using this graph interpretation, we give a direct formula for the generalized Pell numbers. Moreover, we show some identities for these numbers.

The multiplicatively weighted Harary index (\(Hy\)-index) is a new distance-based graph invariant, which was introduced and studied by Deng et al. in [1]. For a connected graph \(G\), the multiplicatively weighted Harary index of \(G\) is defined as \(H_M(G) = \sum\limits_{\{u,v\} \subseteq V(G)} \frac{d_G(u) \cdot d_G(v)}{d_G(u,v)}\), where \(d_G(x)\) denotes the degree of vertex \(x\) and \(d_G(s,t)\) denotes the distance between vertices \(s\) and \(t\) in \(G\). In this paper, we first study a new vertex degree-based graph invariant \(M_2 – \frac{1}{2}M_1\), where \(M_1\) and \(M_2\) are ordinary Zagreb indices. We characterize the trees attaining maximum value of \(M_2 – 4M_1\) among all trees of given order. As applications, we obtain a new proof of Deng et al.’s results on trees with extremal \(H_M\)-index among all trees of given order.

In the current work, the author presents a symbolic algorithm for finding the determinant of any general nonsingular cyclic heptadiagonal matrices and the inverse of anti-cyclic heptadiagonal matrices. The algorithms are mainly based on the work presented in [A. A. Karawia, A New algorithm for inverting general cyclic heptadiagonal matrices recursively, arXiv:1011.2306v1, ICS/SCII]. The symbolic algorithms are suited for implementation using Computer Algebra Systems (CAS) such as MATLAB, MAPLE, and MATHEMATICA. An illustrative example is given.

The Wiener index of a graph is a distance-based topological index defined as the sum of distances between all pairs of vertices. In this paper, two explicit expressions for the expected value of the Wiener indices of two types of random polygonal chains are obtained.

In \([8]\), the author introduced the notion of burst errors for \(2\)-dimensional array coding systems. Also, in \([10]\), the author introduced a series of metrics called Lee-RT-Jain-Metric (LRTJ\)-metric) \([3]\) for array codes, which is a generalization of both classical Lee metric \([12]\) and array \(RT\) metric \([14]\). In this paper, we obtain sufficient conditions on the parameters of array codes equipped with \(LRTJ\)-metric for the identification and correction of burst array errors.

The concept of exterior degree of a finite group \(G\) is introduced by the author in a joint paper [13], which is the probability of randomly selecting two elements \(g\) and \(h\) in \(G\) such that \(g\wedge h = 1\). In the present paper, a necessary and sufficient condition is given for a non-cyclic group when its exterior degree achieves the upper bound \((p^2 + p – 1)/p^3\), where \(p\) is the smallest prime number dividing the order of \(G\). We also compute the exterior degree of all extra-special \(p\)-groups. Finally, for an extra-special \(p\)-group \(H\) and a group \(G\) where \(G/Z^\wedge(G)\) is a \(p\)-group, we will show that \(d^\wedge(G) = d^\wedge(H)\) if and only if \(G/Z^\wedge(G) \cong H/Z^\wedge(H)\), provided that \(d^\wedge(G) \neq 11/32\).

Let \(G\) be a unicyclic graph on \(n \geq 3\) vertices. Let \(A(G)\) be the adjacency matrix of \(G\). The eigenvalues of \(A(G)\) are denoted by \(\lambda_1(G) \geq \lambda_2(G) \geq \cdots \geq \lambda_n(G)\), which are called the eigenvalues of \(G\). Let the unicyclic graphs \(G\) on \(n\) vertices be ordered by their least eigenvalues \(\lambda_n(G)\) in non-decreasing order. For \(n \geq 14\), the first six graphs in this order are determined.

Hyperdomination in hypergraphs was defined by J. John Arul Singh and R. Kala in [3]. Let \(X = \{a_1, a_2, \ldots, a_n\}\) be a finite set and let \(\mathcal{E} = \{E_1, E_2, \ldots, E_m\}\) be a family of subsets of \(X\). \(H = (X, \mathcal{E})\)is said to be a hypergraph if (1) \(E_i \neq \phi\), \(1 \leq i \leq m\), and (2) \(\bigcup_{i=1}^{m} E_i = X\). The elements \(x_1, x_2, \ldots, x_n\) are called the vertices and the sets \(E_1, E_2, \ldots, E_m\) are called the edges. A set \(D \subset X\) is called a hyperdominating set if for each \(v \in X – D\) there exist some edge \(E\) containing \(v\) with \(|E| \geq 2\) such that \(E – v \subset D \neq D\). The hyperdomination number is the minimum cardinality of all hyperdominating sets. In this paper, a finite group is viewed as a hypergraph with vertex set as the elements of the group and edge set as the set of all subgroups of the group. We obtain several bounds for hyperdomination number of finite groups and characterise the extremal graphs in some cases.

Let \(G\) be a simple graph with edge ideal \(I(G)\). In this article, we study the number of pairwise \(3\)-disjoint edges of cycles and complements of triangle-free graphs. Using that, we determine the Castelnuovo-Mumford regularity of \(R/I(G)\) for the above classes of graphs according to the number of pairwise \(3\)-disjoint edges.

The Merrifield-Simmons index \(i(G)\) of a graph \(G\) is defined as the total number of independent sets of \(G\). A connected graph \(G = (V,E)\) is called a quasi-unicyclic graph if there exists a vertex \(u_0 \in V\) such that \(G – u_0\) is a unicyclic graph. Denote by \(\mathcal{U}(n,d_0)\) the set of quasi-unicyclic graphs of order \(n\) with \(G – u_0\) being a unicyclic graph and \(d_G(u_0) = d_0\). In this paper, we characterize the quasi-unicyclic graphs with the smallest, the second-smallest, the largest, and the second-largest Merrifield-Simmons indices, respectively, in \(\mathcal{U}(n, d_0)\).

A unicyclic map is a rooted planar map such that there is only one cycle which is the boundary of the unique inner face (the inner face contains no trees) and the root-vertex is on the cycle. In this paper we investigate the number of unicyclic maps and present some formulae for such maps with up to three parameters: the number of edges and the valencies of the root-vertex and the root-face.

Brualdi and Massey in \(1993\) posed two conjectures regarding the upper bound for incidence coloring number of graphs in terms of maximum degree. In this paper among some results, we prove these conjectures for some classes of graphs with maximum degree \(4\).

P. Erdős, F. Harary, and M. Klawe studied the \(K_n\)-residual graph and came up with some conjectures and conclusions about the \(m-K_n\)-residual graph. For connected \(m-K_2\)-residual graphs, they constructed an \(m-K_2\)-residual graph of order \(3m+2\) and proposed that \(3m+2\) is the minimum order, which remained unproven. In this paper, using operation properties of sets and other methods, we prove that the minimum order of connected \(m-K_2\)-residual graphs is indeed \(3m+2\).

In this paper, we present explicit formulas for domination numbers of equidistant \(m\)-cactus chains and find the corresponding minimum dominating sets. For an arbitrary \(m\)-cactus chain, we establish the lower and upper bounds for its domination number. We find some extremal chains with respect to this graph invariant.

A strongly connected digraph \(D\) is said to be maximally arc connected if its arc-connectivity \(\lambda(D)\) attains its minimum degree \(\delta(D)\). For any vertex \(x\) of \(D\), the set \(\{x^g \mid g \in \text{Aut}(D)\}\) is called an orbit of \(\text{Aut}(D)\). Liu and Meng [ Fengxia Liu, Jixiang Meng, Edge-Connectivity of regular graphs with two orbits, Discrete Math. \(308 (2008) 3711-3717 \)] proved that the edge-connectivity of a \(k\)-regular connected graph with two orbits and girth \(\geq 5\) attains its regular degree \(k\). In the present paper, we prove the existence of \(k\)-regular \(m\)-arc-connected digraphs with two orbits for some given integer \(k\) and \(m\). Furthermore, we prove that the \(k\)-regular connected digraphs with two orbits, satisfying girth \( \geq k\) are maximally arc connected. Finally, we give an example to show that the girth bound \(k\) is best possible.

There are \(267\) nonisomorphic groups of order \(64\). It was known that \(259\) of these groups admit \((64, 28, 12)\) difference sets. In \([4]\), the author found all \((64, 28, 12)\) difference sets in \(111\) groups. In this paper, we find all \((64, 28, 12)\) difference sets in all the remaining groups of order \(64\) that admit \((64, 28, 12)\) difference sets. Also, we find all nonisomorphic symmetric \((64, 28, 12)\) designs that arise from these difference sets. We use these \((64, 28, 12)\) difference sets to construct all \((64, 27, 10, 12)\) and \((64, 28, 12, 12)\) partial difference sets. Finally, we examine the corresponding strongly regular graphs with parameters \((64, 27, 10, 12)\) and \((64, 28, 12, 12)\).

For a simple undirected graph \(G = (V, E)\), a subset \(I\) of \(V(G)\) is said to be an independent set of \(G\) if any two vertices in \(I\) are not adjacent in \(G\). A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we survey the largest to fourth largest numbers of maximal independent sets among all trees and forests. In addition, we further look into the problem of determining the fifth largest number of maximal independent sets among all trees and forests. Extremal graphs achieving these values are also given.