Motzkin posed the problem of finding the maximal density $\mu (M)$ of sets of integers in which the differences given by a set $M$ do not occur. The problem is already settled when $|M|\le 2$ or $M$ is a finite arithmetic progression. In this paper, we determine $\mu (M)$ when $M$ has some other structure. For example, we determine $\mu (M)$ when $M$ is a finite geometric progression.

For vertices $u,v$ in a connected graph $G$, a $u-v$ chordless path in $G$ is a $u-v$ monophonic path. The monophonic interval $J_G[u,v]$ consists of all vertices lying on some $u-v$ monophonic path in $G$. For $S\subseteq V(G)$, the set $J_G[S]$ is the union of all sets $J_G[u,v]$ for $u,v\in S$. A set $S\subseteq V(G)$ is a monophonic set of $G$ if $J_G[S]=V(G)$. The cardinality of a minimum monophonic set of $G$ is the monophonic number of $G$, denoted by $mn(G)$. In this paper, bounds for the monophonic number of the strong product graphs are obtained, and for several classes, improved bounds and exact values are obtained.

A hypergraph is a useful tool to model complex systems and can be considered a natural generalization of graphs. In this paper, we define some operations of fuzzy hypergraphs and strong fuzzy $r$-uniform hypergraphs, such as Cartesian product, strong product, normal product, lexicographic product, union, and join. We prove that if a hypergraph $H$ is formed by one of these operations, then this hypergraph is a fuzzy hypergraph or a strong fuzzy $r$-uniform hypergraph. Finally, we discuss an application of fuzzy hypergraphs.

Let $p_e(n)$ be the number of ways to make change for $n$ cents using pennies, nickels, dimes, and quarters. By manipulating the generating function for $p_e(n)$, we prove that the sequence $\{p_e(n)(\mathrm{mod}{\ell }^j)\}$ is periodic for every prime power $\ell$.

In 1972, Chvatal and Erdős showed that the graph $G$ with independence number $\alpha (G)$ no more than its connectivity $\kappa (G)$ (i.e., $\kappa (G)\ge \alpha (G)$) is hamiltonian. In this paper, we consider a kind of Chvatal and Erdős type condition on edge-connectivity $\lambda (G)$ and matching number (edge independence number). We show that if $\lambda (G)\ge {\alpha }^{\prime }(G)–1$, then $G$ is either supereulerian or in a well-defined family of graphs. Moreover, we weaken the condition $\kappa (G)\ge \alpha (G)–1$ in [11] to $\lambda (G)\ge \alpha (G)–1$ and obtain a similar characterization on non-supereulerian graphs. We also characterize the graph which contains a dominating closed trail under the assumption $\lambda (G)\ge {\alpha }^{\prime }(G)–2$.

The coloring number $col(G)$ of a graph $G$ is the smallest number $k$ for which there exists a linear ordering of the vertices of $G$ such that each vertex is preceded by fewer than $k$ of its neighbors. It is well known that $\chi (G)\le col(G)$ for any graph $G$, where $\chi (G)$ denotes the chromatic number of $G$. The Randić index $R(G)$ of a graph $G$ is defined as the sum of the weights $\frac{1}{\sqrt{d(u)d(v)}}$ of all edges $uv$ of $G$, where $d(u)$ denotes the degree of a vertex $u$ in $G$. We show that $\chi (G)\le col(G)\le 2R^{\prime }(G)\le R(G)$ for any connected graph $G$ with at least one edge, and $col(G)=2R^{\prime }(G)$ if and only if $G$ is a complete graph with some pendent edges attaching to its same vertex, where $R^{\prime }(G)$ is a modification of Randić index, defined as the sum of the weights $\frac{1}{max\{d(u),d(v)\}}$ of all edges $uv$ of $G$. This strengthens a relation between Randić index and chromatic number by Hansen et al. [7], a relation between Randić index and coloring number by Wu et al. [17] and extends a theorem of Deng et al. [2].

For any vertex $x$ in a connected graph $G$ of order $n\ge 2$, a set $S\subseteq V(G)$ is a $z$-detour monophonic set of $G$ if each vertex $v\in V(G)$ lies on a $x-y$ detour monophonic path for some element $y\in S$. The minimum cardinality of a $x$-detour monophonic set of $G$ is the $x$-detour monophonic number of $G$, denoted by $d{m}_z(G)$. An $x$-detour monophonic set $S_x$ of $G$ is called a minimal $x$-detour monophonic set if no proper subset of $S_x$ is an $x$-detour monophonic set. The upper $x$-detour monophonic number of $G$, denoted by $d{m}_x^{+}(G)$, is defined as the maximum cardinality of a minimal $x$-detour monophonic set of $G$. We determine bounds for it and find the same for some special classes of graphs. For positive integers $r,d,$ and $k$ with $2\le r\le d$ and $k\ge 2$, there exists a connected graph $G$ with monophonic radius $r$, monophonic diameter $d$, and upper $z$-detour monophonic number $k$ for some vertex $x$ in $G$. Also, it is shown that for positive integers $j,k,l,$ and $n$ with $2\le j\le k\le l\le n–7$, there exists a connected graph $G$ of order $n$ with $d{m}_x(G)=j$, $d{m}_x^{+}(G)=l$, and a minimal $x$-detour monophonic set of cardinality $k$.

Many authors define certain generalizations of the usual Fibonacci, Pell, and Lucas numbers by matrix methods and then obtain the Binet formulas and combinatorial representations of the generalizations of these number sequences. In this article, we firstly define and study the generalized Gaussian Fibonacci numbers and then find the matrix representation of the generalized Gaussian Fibonacci numbers and prove some theorems by these matrix representations.

Given two sets $A,B\subset {\mathbb{F}}_q$, of elements of the finite field ${\mathbb{F}}_q$, of $q$ elements, Shparlinski (2008) showed that the product set $\mathcal{A}\mathcal{B}=\{ab\mid a\in \mathcal{A},b\in \mathcal{B}\}$ contains an arithmetic progression of length $k\ge 3$ provided that \(k

3\) is the characteristic of $\mathbb{F}$, and $|\mathcal{A}||\mathcal{B}|\ge 2q^{2-1/(k-1)}$. In this paper, we recover Shparlinski’s result for the case of 3-term arithmetic progressions via spectra of product graphs over finite fields. We also illustrate our method in the setting of residue rings. Let $m$ be a large integer and $\mathbb{Z}/m\mathbb{Z}$ be the ring of residues mod $m$. For any two sets $\mathcal{A},\mathcal{B}\subset \mathbb{Z}/m\mathbb{Z}$ of cardinality $$|\mathcal{A}||\mathcal{B}|>m(\frac{r(m)m}{r(m{)}^{\frac{1}{2}}+1})$$, the product set $\mathcal{A}\mathcal{B}$ contains a $3$-term arithmetic progression, where $r(m)$ is the smallest prime divisor of $m$ and $r(m)$ is the number of divisors of $m$. The spectral proofs presented in this paper avoid the use of character and exponential sums, the usual tool to deal with problems of this kind.

A proper edge-coloring of a graph $G$ with colors $1,\dots ,t$ is called an interval $t$-coloring if the colors of edges incident to any vertex of $G$ form an interval of integers. A graph $G$ is interval colorable if it has an interval $t$-coloring for some positive integer $t$. For an interval colorable graph $G$, the least value of $t$ for which $G$ has an interval $t$-coloring is denoted by $w(G)$. A graph $G$ is outerplanar if it can be embedded in the plane so that all its vertices lie on the same (unbounded) face. In this paper, we show that if $G$ is a 2-connected outerplanar graph with $\mathrm{\Delta }(G)=3$, then $G$ is interval colorable and $$w(G)=\{\begin{array}{ll}3,& \text{if }|V(G)|\text{ is even},\\ 4,& \text{if }|V(G)|\text{ is odd}.\end{array}$$
We also give a negative answer to the question of Axenovich on the outerplanar triangulations.

In this paper, we characterize all finite abelian groups with isomorphic intersection graphs. This solves a conjecture proposed by $B$.Zelinka.

This paper devotes to solving the following conjecture proposed by Gvozdjak: “An $(a,b;n)$-graceful labeling of $P_n$ exists if and only if the integers $a,b,n$ satisfy (1) $b–a$ has the same parity as $n(n+1)/2$; (2) $0<|b–a|\le (n+1)/2$ and (3) $n/2\le a+b\le 3n/2$.'' Its solving can shed some new light on solving the famous Oberwolfach problem. It is shown that the conjecture is true for every $n$ if the conjecture is true when $n\le 4a+1$ and $a$ is a fixed value. Moreover, we prove that the conjecture is true for $a=0,1,2,3,4,5,6$.

The aim of this paper is to show that the corona $P_n⨀P_m$ between two paths $P_n$ and $P_m$ is cordial for all $n\ge 1$ and $m\ge 1$. Also, we prove that except for $n$ and $m$ being congruent to $2(\mathrm{mod}4)$, the corona $C_n⨀C_m$ between two cycles $C_n$ and $C_m$ is cordial. Furthermore, we show that if $n\equiv 2(\mathrm{mod}4)$ and $m$ is odd, then $C_n⨀C_m$ is not cordial.

In this paper, we establish some general identities involving the weighted row sums of a Riordan array and hyperharmonic numbers. From these general identities, we deduce some particular identities involving other special combinatorial sequences, such as the Stirling numbers, the ordered Bell numbers, the Fibonacci numbers, the Lucas numbers, and the binomial coefficients.

In this paper, we consider the relationship between toughness and the existence of $[a,b]$-factors with inclusion/exclusion properties. We obtain that if $t(G)\ge a–1+\frac{a–1}{b}$ with $b>a>2$, where $a,b$ are two integers, then for any two given edges $e_1$ and $e_2$, there exist an $[a,b]$-factor including $e_1,e_2$; and an $[a,b]$-factor including $e_1$ and excluding $e_2$; as well as an $(a,b)$-factor excluding $e_1,e_2$. Furthermore, it is shown that the results are best possible in some sense.

In this paper, we will determine the NBB bases with respect to a certain standard ordering of atoms of lattices of $321$-$312$-$231$-avoiding permutations and of $321$-avoiding permutations with the weak Bruhat order. Using our expressions of NBB bases, we will calculate the Möbius numbers of these lattices. These values are shown to be related to Fibonacci polynomials.

Let $D(G)$ denote the signless Dirichlet spectral radius of the graph $G$ with at least a pendant vertex, and ${\pi }_1$ and ${\pi }_2$ be two nonincreasing unicyclic graphic degree sequences with the same frequency of number $1$. In this paper, the signless Dirichlet spectral radius of connected graphs with a given degree sequence is studied. The results are used to prove a majorization theorem of unicyclic graphs. We prove that if ${\pi }_1⊵{\pi }_2$, then $D(G_1)\le D(G_2)$ with equality if and only if ${\pi }_1={\pi }_2$, where $G_1$ and $G_2$ are the graphs with the largest signless Dirichlet spectral radius among all unicyclic graphs with degree sequences ${\pi }_1$ and ${\pi }_2$, respectively. Moreover, the graphs with the largest signless Dirichlet spectral radius among all unicyclic graphs with $k$ pendant vertices are characterized.

A function $f$ is called a graceful labeling of a graph $G$ with $m$ edges, if $f$ is an injective function from $V(G)$ to $\{0,1,2,\dots ,m\}$ such that when every edge $uv$ is assigned the edge label $|f(u)–f(v)|$, then the resulting edge labels are distinct. A graph which admits a graceful labeling is called a graceful graph. A graceful labeling of a graph $G$ with $m$ edges is called an $\alpha$-labeling if there exists a number $\alpha$ such that for any edge $uv$, $min\{f(u),f(v)\}\le \lambda <max\{f(u),f(v)\}$. The characterization of graceful graphs appears to be a very difficult problem in Graph Theory. In this paper, we prove a basic structural property of graceful graphs, that every tree is a subtree of a graceful graph, an $\alpha$-labeled graph, and a graceful tree, and we discuss a related open problem towards settling the popular Graceful Tree Conjecture.

We use rook placements to prove Spivey’s Bell number formula and other identities related to it, in particular, some convolution identities involving Stirling numbers and relations involving Bell numbers. To cover as many special cases as possible, we work on the generalized Stirling numbers that arise from the rook model of Goldman and Haglund. An alternative combinatorial interpretation for the Type II generalized $q$-Stirling numbers of Remmel and Wachs is also introduced, in which the method used to obtain the earlier identities can be adapted easily.

An $H$-triangle is a triangle with corners in the set of vertices of a tiling of ${\mathbb{R}}^2$ by regular hexagons of unit edge. Let $b(\mathrm{\Delta })$ be the number of the boundary $H$-points of an $H$-triangle $\mathrm{\Delta }$. In [3] we made a conjecture that for any $H$-triangle with $k$ interior $H$-points, we have $b(\mathrm{\Delta })\in \{3,4,\dots ,3k+4,3k+5,3k+7\}$. In this note, we prove the conjecture is true for $k=4$, but not true for $k=5$ because $b(\mathrm{\Delta })$ cannot equal $15$.

For a positive integer $d\ge 1$, an $L(d,1)$-labeling of a graph $G$ is an assignment of nonnegative integers to $V(G)$ such that the difference between labels of adjacent vertices is at least $d$, and the difference between labels of vertices that are distance two apart is at least $1$. The span of an $L(d,1)$-labeling of a graph $G$ is the difference between the maximum and minimum integers used by it. The minimum span of an $L(d,1)$-labeling of $G$ is denoted by $\lambda (G)$. In [17], we obtained that $r\mathrm{\Delta }+1\le \lambda (G(r{P}_5))\le r\mathrm{\Delta }+2$, $\lambda (G(r{P}_k))=r\mathrm{\Delta }+1$ for $k\ge 6$; and $\lambda (G(r{P}_4))\le (\mathrm{\Delta }+1)r+1$, $\lambda (G(r{P}_3))\le (\mathrm{\Delta }+1)r+\mathrm{\Delta }$ for any graph $G$ with maximum degree $\mathrm{\Delta }$. In this paper, we will focus on $L(d,1)$-labelings of the edge-multiplicity-path-replacement $G(r{P}_k)$ of a graph $G$ for $r\ge 2$, $d\ge 3$, and $k\ge 3$. And we show that the class of graphs $G(r{P}_k)$ with $k\ge 3$ satisfies the conjecture proposed by Havet and Yu [7].

Let $R$ be a commutative ring with non-zero identity. The cozero-divisor graph of $R$, denoted by ${\mathrm{\Gamma }}^{\prime }(R)$, is a graph with vertex-set $W^{\ast }(R)$, which is the set of all non-zero non-unit elements of $R$, and two distinct vertices $a$ and $b$ in $W^{\ast }(R)$ are adjacent if and only if $a\notin Rb$ and $b\notin Ra$, where for $c\in R$, $Rc$ is the ideal generated by $c$. In this paper, we completely determine all finite commutative rings $R$ such that ${\mathrm{\Gamma }}^{\prime }(R)$ is planar, outerplanar and a ring graph.

The Wiener index is the sum of distances between all pairs of vertices in a connected graph. A cactus is a connected graph in which any two of its cycles have at most one common vertex. In this article, we present some graphic transformations and derive the formulas for calculating the Wiener index of new graphs. With these transformations, we characterize the graphs having the smallest Wiener index among all cacti given matching number and cycle number.

A Roman dominating function on a graph $G$ is a function $f:V(G)\to \{0,1,2\}$ satisfying the condition that every vertex $u$ of $G$ for which $f(u)=0$ is adjacent to at least one vertex $v$ of $G$ for which $f(v)=2$. The weight of a Roman dominating function is the value $f(V(G))=\sum _{u\in V(G)}f(u)$. The Roman domination number, ${\gamma }_R(G)$, of $G$ is the minimum weight of a Roman dominating function on $G$. A graph $G$ is said to be Roman domination edge critical, or simply ${\gamma }_R$-edge critical, if ${\gamma }_R(G+e)<{\gamma }_R(G)$ for any edge $e\notin E(G)$. In this paper, we characterize all ${\gamma }_R$-edge critical connected graphs having precisely two cycles.

An $h$-edge-coloring (block-coloring) of type $s$ of a graph $G$ is an assignment of $h$ colors to the edges (blocks) of $G$ such that for every vertex $x$ of $G$, the edges (blocks) incident with $x$ are colored with $s$ colors. For every color $i$, ${\xi }_{x,i}$ (${\mathcal{B}}_{x,i}$) denotes the set of all edges (blocks) incident with $x$ and colored by $i$. An $h$-edge-coloring ($h$-block-coloring) of type $s$ is equitable if for every vertex $x$ and for colors $i$, $j$, $||{\xi }_{x,i}|–|{\xi }_{x,j}||\le 1$ ($||{\mathcal{B}}_{x,i}|–|{\mathcal{B}}_{x,j}||\le 1$). In this paper, we study the existence of $h$-edge-colorings of type $s=2,3$ of $K_t$ and then show that the solution of this problem induces the solution of the existence of a $C_4$-${}_t{K}_2$-design having an equitable $h$-block-coloring of type $s=2,3$.

G. Chartrand et al. [3] define a graph $G$ without isolated vertices to be the least common multiple (lcm) of two graphs $G_1$ and $G_2$ if $G$ is a graph of minimum size such that $G$ is both $G_1$-decomposable and $G_2$-decomposable. A bi-star $B_{m,n}$ is a caterpillar with spine length one. In this paper, we discuss a good lower bound for $lcm(B_{m,n},G)$, where $G$ is a simple graph. We also investigate $lcm(B_{m,n},r{K}_2)$ and provide a good lower bound and an appropriate upper bound for $lcm(B_{m,n},P_{r+1})$ for all $m\ge 1$, $n\ge 1$, and $r\ge 1$.

A path in an edge-colored graph is said to be a rainbow path if no two edges on the path share the same color. An edge-colored graph $G$ is rainbow connected if there exists a $u-v$ rainbow path for any two vertices $u$ and $v$ in $G$. The rainbow connection number of a graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. For any two vertices $u$ and $v$ of $G$, a rainbow $u-v$ geodesic in $G$ is a rainbow $u$–$v$ path of length $d(u,v)$, where $d(u,v)$ is the distance between $u$ and $v$. The graph $G$ is strongly rainbow connected if there exists a rainbow $u-v$ geodesic for any two vertices $u$ and $v$ in $G$. The strong rainbow connection number of $G$, denoted by $src(G)$, is the smallest number of colors that are needed in order to make $G$ strongly rainbow connected.

In this paper, we determine the precise (strong) rainbow connection numbers of ladders and Möbius ladders. Let $p$ be an odd prime; we show the (strong) rainbow connection numbers of Cayley graphs on the dihedral group $D_{2p}$ of order $2p$ and the cyclic group ${\mathbb{Z}}_{2p}$ of order $2p$. In particular, an open problem posed by Li et al. in [8] is solved.

Given a collection of graphs $\mathcal{H}$, an $\mathcal{H}$-decomposition of $\lambda K_v$ is a decomposition of the edges of $\lambda K_v$ into isomorphic copies of graphs in $\mathcal{H}$. A kite is a triangle with a tail consisting of a single edge. In this paper, we investigate the decomposition problem when $\mathcal{H}$ is the set containing a kite and a $4$-cycle, that is, this paper gives a complete solution to the problem of decomposing $\lambda K_v$ into $r$ kites and $s$ $4$-cycles for every admissible values of $v$, $r,\lambda$, and $s$.

A $b$-coloring of a graph $G$ with $k$ colors is a proper coloring of $G$ using $k$ colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer $k$ for which $G$ has a $b$-coloring using $k$ colors is the $b$-chromatic number $\beta (G)$ of $G$. The $b$-spectrum ${\mathcal{S}}_b(G)$ of a graph $G$ is the set of positive integers $k$, $\chi (G)\le k\le b(G)$, for which $G$ has a $b$-coloring using $k$ colors. A graph $G$ is $b$-continuous if ${\mathcal{S}}_b(G)=\{\chi (G),\dots ,b(G)\}$. It is known that for any two graphs $G$ and $H$, $b(G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H)\ge max\{b(G),b(H)\}$, where $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$ stands for the Cartesian product. In this paper, we determine some families of graphs $G$ and $H$ for which $b(G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H)\ge b(G)+b(H)–1$. Further, we show that if $O_k,i=1,2,\dots ,n$ are odd graphs with $k_i\ge 4$ for each $i$, then $O_{k_1}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{O}_{k_2}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}\dots \mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{O}_{k_n}$ is $b$-continuous and $b(O_{k_1}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{O}_{k_2}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}\dots \mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{O}_{k_n})=1+\sum _{i=1}^n{k}_i$.

We study the number of elements $x$ and $y$ of a finite group $G$ such that $x\otimes y=1_{G\oplus G}$ in the nonabelian tensor square $G\otimes G$ of $G$. This number, divided by $|G{|}^2$, is called the tensor degree of $G$ and has connections with the exterior degree, introduced a few years ago in [P. Niroomand and R. Rezaei, On the exterior degree of finite groups, Comm. Algebra $39(2011),335–343$]. The analysis of upper and lower bounds of the tensor degree allows us to find interesting structural restrictions for the whole group.

For a (molecular) graph $G$, the general sum-connectivity index ${\chi }_{\alpha }(G)$ is defined as the sum of the weights $(d_u+d_v{)}^{\alpha }$ of all edges $uv$ of $G$, where $d_u$ (or $d_v$) denotes the degree of a vertex $u$ (or $v$) in $G$ and $\alpha$ is an arbitrary real number. In this paper, we give an efficient formula for computing the general sum-connectivity index of polyomino chains and characterize the extremal polyomino chains with respect to this index, which generalizes one of the main results in [Z. Yarahmadi, A. Ashrafi, S. Moradi, Extremal polyomino chains with respect to Zagreb indices, Appl. Math. Lett. 25 (2012): 166-171].

In this paper, we investigate the basis number for the wreath product of wheels with paths. Also, as a related problem, we construct a minimum cycle basis of the same.

Let$ex(m,C_{\le n})$ denote the maximum size of a graph of order $m$ and girth at least $n+1$, and $EX(m,C_{\le n})$ be the set of all graphs of girth at least $n+1$ and size $ex(m,C_{\le n})$. The Ramsey number $R(C_{\le n},K_m)$ is the smallest $k$ such that every graph of order $k$ contains either a cycle of order $n$ for some $3\le l\le n$ or a set of $m$ independent vertices. It is known that $ex(2n,C_{\le n})=2n+2$ for $n\ge 4$, and the exact values of $R(C_{\le n},K_m)$ for $n\ge m$ are known. In this paper, we characterize all graphs in $EX(2n,C_{\le n})$ for $n\ge 5$, and then obtain the exact values of $R(C_{\le n},K_m)$ for $m\in \{n,n+1\}$.

Since their desirable features, variable-weight optical orthogonal codes (VWOOCs) have found wide ranges of applications in various optical networks and systems. In recent years, optimal $2$-CP$(W,1,Q;n)$s are used to construct optimal VWOOCs. So far, some works have been done on optimal $2$-CP$(W,1,Q;n)$s with $w_{max}\le 6$, where $w_{max}=max\{w:w\in W\}$. As far as the authors are aware, little is known for explicit constructions of optimal $2$-CP$(W,1,Q;n)$s with $w_{max}\ge 7$ and $|W|=3$. In this paper, two explicit constructions of $2$-CP$(\{3,4,7\},1,Q;n)$s are given, and two new infinite classes of optimal VWOOCs are obtained.

In this study, it has been researched which Euclidean regular polyhedrons are also taxicab regular and which are not. The existence of non-Euclidean taxicab regular polyhedrons in the taxicab $3$-space has also been investigated.

As a generalization of attenuated space, the concept of singular linear spaces was firstly introduced in [1]. In this paper, we construct a family of error-correcting pooling designs with the incidence matrix of two types of subspaces of singular linear space over finite fields, and exhibit their disjunct properties. Moreover, we show that the new construction gives better ratio of efficiency than the former ones under certain conditions. Finally, the paper gives a brief introduction about the relationship between the columns (rows) of the matrix and the related parameters.

A map is unicursal if all its vertices are even-valent except two odd-valent vertices. This paper investigates the enumeration of rooted nonseparable unicursal planar maps and provides two functional equations satisfied by its generating functions with the number of nonrooted vertices, the number of inner faces (or the number of edges) and the valencies of the two odd vertices of maps as parameters.

Let ${\sigma }_k(G)$ denote the minimum degree sum of $k$ independent vertices of a graph $G$. A spanning tree with at most $3$ leaves is called a spanning $3$-ended tree. In this paper, we prove that for any $k$-connected claw-free graph $G$ with $|G|=n$, if ${\sigma }_{k+3}(G)\ge n–k$, then $G$ contains a spanning $3$-ended tree.

As a promotion of the channel assignment problem, an $L(1,1,1)$-labeling of a graph $G$ is an assignment of nonnegative integers to $V(G)$ such that the difference between labels of adjacent vertices is at least $1$, and the difference between labels of vertices that are distance two and three apart is at least $1$. About $10$ years ago, many mathematicians considered colorings (proper, general, total or from lists) such that vertices (all or adjacent) are distinguished either by sets or multisets or sums. In this paper, we will study $L(1,1,1)$-labeling-number and $L(1,1)$-edge-labeling-number of the edge-path-replacement. From this, we will consider the total-neighbor-distinguishing coloring and the neighbor-distinguishing coloring of the edge-multiplicity-paths-replacements, give a reference for the conjectures: ${\text{tndis-}}_{\mathrm{\Sigma }}(G)\le \mathrm{\Delta }+3$, ${\text{ndi}}_{\mathrm{\Sigma }}(G)\le \mathrm{\Delta }+2$, and ${\text{tndi}}_S(G)\le \mathrm{\Delta }+3$ for the edge-multiplicity-paths-replacements $G(r{P}_k)$ with $k\ge 3$ and $r\ge 1$.

A $T$-shape tree is a tree with exactly one of its vertices having maximal degree $3$. In this paper, we consider a class of tricyclic graphs which is obtained from a $T$-shape tree by attaching three identical odd cycles $C_{k}s$ to three vertices of degree $1$ of the $T$-shape tree, respectively, where $k\ge 3$ is odd. It is shown that such graphs are determined by their adjacency spectrum.

In this paper, we have proved that if a contraction critical $8$-connected graph $G$ has no vertices of degree $8$, then for every vertex $x$ of $G$, either $x$ is adjacent to a vertex of degree $9$, or there are at least $4$ vertices of degree $9$ such that every one of them is at distance $2$ from $x$.

The crossing number of a graph $G$ is the minimum number of pairwise intersections of edges in a drawing of $G$. The $n$-dimensional locally twisted cubes $LT{Q}_n$, proposed by X.F. Yang, D.J. Evans and G.M. Megson, is an important interconnection network with good topological properties and applications. In this paper, we mainly obtain an upper bound on the crossing number of $LT{Q}_n$, no more than $\frac{265}{6}{4}^{n-4}–(n^2+\frac{15+(-1{)}^{n-1}}{6}{2}^{n-3}$.

Let $G$ be an infinite geometric graph; in particular, a graph whose vertices are a countable discrete set of points on the plane, with vertices $u,v$ adjacent if their Euclidean distance is less than 1. A “fire” begins at some finite set of vertices and spreads to all neighbors in discrete steps; in the meantime, $f$ vertices can be deleted at each time-step. Let $f(G)$ be the least $f$ for which any fire on $G$ can be stopped in finite time. We show that if $G$ has bounded density, in the sense that no open disk of radius $r$ contains more than $\lambda$ vertices, then $f(G)$ is bounded above by ceiling of a universal constant times $\frac{\lambda }{r^2}$. Similarly, if the density of $G$ is bounded from below in the sense that every open disk of radius $r$ contains at least $\beta$ vertices, then $f(G)$ is bounded below by $\kappa$ times the square of the floor of a universal constant times $\frac{1}{r}$.

Let $G$ be a graph, and let $k\ge 2$ be an integer. A graph $G$ is fractional independent-set-deletable $k$-factor-critical (in short, fractional ID-$k$-factor-critical) if $G–I$ has a fractional $k$-factor for every independent set $I$ of $G$. In this paper, a Fan-type condition for fractional ID-$k$-factor-critical graphs is given.

The crossing number of a graph $G$ is the smallest number of pairwise crossings of edges among all the drawings of $G$ in the plane. The pancake graph is an important network topological structure for interconnecting processors in parallel computers. In this paper, we prove the exact crossing number of the pancake graph $P_4$ is six.

A planar graph is called $C_4$-free if it has no cycles of length four. Let $f(n,C_4)$ denote the maximum size of a $C_4$-free planar graph with order $n$. In this paper, it is shown that $f(n,C_4)=\lfloor \frac{15}{7}(n-2)\rfloor –\mu$ for $n\ge 30$, where $\mu =1$ if $n\equiv 3(\mathrm{mod}7)$ or $n=32,33,37$, and $\mu =0$ otherwise.

The Harary spectral radius $\rho (G)$ of a graph $G$ is the largest eigenvalue of the Harary matrix $RD(G)$. In this paper, we determine graphs with the largest Harary spectral radius in four classes of simple connected graphs with $n$ vertices: with given matching number, vertex connectivity, edge connectivity, and chromatic number, respectively.

We consider the relationship between the minimum degree $\delta (G$ of a graph and the complexity of recognizing if a graph is $T$-tenacious. Let $T\ge 1$ be a rational number. We first show that if $\delta (G)\ge \frac{Tn}{T+1}$ then $G$ is $T$-tenacious. On the other hand, for any fixed $ϵ>0$, we show that it is NP-hard to determine if $G$ is $T$-tenacious, even for the class of graphs with $\delta (G)\ge (\frac{T}{T+1}–ϵ)n$.

Let $G$ be a finite group and let $S$ be a nonempty subset of $G$. For any positive integer $k$, let $S^k$ be the subset product given by the set $\{s_1\cdots s_k\mid s_1,\dots ,s_k\in S\}$. If there exists a positive integer $n$ such that $S^n=G$, then $S$ is said to be exhaustive. Let $e(S)$ denote the smallest positive integer $n$, if it exists, such that $S^n=G$. We call $e(S)$ the exhaustion number of the set $S$. If $S^n\ne G$ for any positive integer $n$, then $S$ is said to be non-exhaustive. In this paper, we obtain some properties of exhaustive and non-exhaustive subsets of finite groups.

A graph $G$ is called $H$-equipackable if every maximal $H$-packing in $G$ is also a maximum $H$-packing in $G$. In 2012, $P_k$-equipackable paths and cycles, $M_k$-equipackable paths and cycles are characterized. In this paper, $P_m\cup P_k$-equipackable paths and cycles are characterized.