A graphic sequence $\pi =(d_1,d_2,\dots ,d_n)$ is said to be potentially $K_{1^3,4}$-graphic if there is a realization of $\pi$ containing $K_{1^3,4}$ as a subgraph, where $K_{1^3,4}$ is the $1\times 1\times 1\times 4$ complete 4-partite graph. In this paper, we characterize the graphic sequences potentially $K_{1^3,4}$-graphic and the result is simple. In addition, we apply this characterization to compute the values of $\sigma (K_{1^3,4},n)$.

We show, using a hybrid analysis/linear algebra argument, that the diagonal vector of an infinite symmetric matrix over ${\mathbb{Z}}_2$ is contained in the range of the matrix. We apply this result to an extension, to the countably infinite case, of the Lights Out problem.

Given a distribution of pebbles on the vertices of a connected graph $G$, a pebbling move on $G$ consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The $t$-pebbling number ${\pi }_t(G)$ is the smallest positive integer such that for every distribution of ${\pi }_t(G)$ pebbles and every vertex $v$, $t$ pebbles can be moved to $v$. For $t=1$, Graham conjectured that ${\pi }_1(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)\le {\pi }_1(G){\pi }_1(H)$ for any connected graphs $G$ and $H$, where $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$ denotes the Cartesian product of $G$ and $H$. Herscovici further conjectured that ${\pi }_{st}(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)\le {\pi }_s(G){\pi }_t(H)$ for any positive integers $s$ and $t$. Lourdusamy [A. Lourdusamy, “$t$-pebbling the product of graphs”, Acta Ciencia Indica, XXXII(1)(2006), 171-176] also conjectured that ${\pi }_t(C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n)\le {\pi }_1(C_m){\pi }_t(C_n)$ for cycles $C_m$ and $C_n$. In this paper, we show that ${\pi }_{st}(C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n)\le {\pi }_s(C_m){\pi }_t(C_n)$, which confirms this conjecture due to Lourdusamy.

The enhanced hypercube is basically a hypercube with additional edges augmented, where the additional edges connect all pairs of complementary nodes in the hypercube. Taking into account the minimal routing function and the structural properties of the enhanced hypercube, $n+1$ internal disjoint paths from one node to other distinct $n+1$ nodes have been constructed in an $n$-dimensional enhanced hypercube. The results can be used to provide an efficient and reliable routing to avoid congestion, accelerate transmission rate, and provide alternative transmission routes in enhanced hypercube networks, thus remarkably improving the performance of the interconnect networks.

The newly introduced neighborhood matrix extends the power of adjacency and distance matrices to describe the topology of graphs. The adjacency matrix enumerates which pairs of vertices share an edge and it may be summarized by the degree sequence, a list of the adjacency matrix row sums. The distance matrix shows more information, namely the length of shortest paths between vertex pairs. We introduce and explore the neighborhood matrix, which we have found to be an analog to the distance matrix what the degree sequence is to the adjacency matrix. The neighbor matrix includes the degree sequence as its first column and the sequence of all other distances in the graph up to the graph’s diameter, enumerating the number of neighbors each vertex has at every distance present in the graph. We prove this matrix to contain eleven oft-used graph statistics and topological descriptors. We also provide insight into two applications that show potential utility of the neighbor matrix in comparing graphs and identifying topologically significant vertices in a graph.

In this paper, for the Catalan-Larcombe-French sequence $\{P_n{\}}_{n\ge 0}$ and the Fennessey-Larcombe-French sequence $\{V_n{\}}_{n\ge 0}$, we mainly discuss the log-behavior of some sequences related to $\{P_n{\}}_{n\ge 0}$ and $\{V_n{\}}_{n\ge 0}$. For example, we study the log-behavior of some sequences such as $\{P_n^2{\}}_{n\ge 0}$, $\{n!n{V}_n{\}}_{n\ge 1}$, $\{n!V_n{\}}_{n\ge 0}$, and $\{V_n-P_n{\}}_{n\ge 2}$. In addition, we discuss the monotonicity of some sequences involving $\{P_n{\}}_{n\ge 0}$ and $\{V_n{\}}_{n\ge 0}$.

A graph $G$ of order $|V(G)|$ and size $|E(G)|$ is called edge-magic if there exists a bijection $f:V(G)\cup E(G)\to \{1,2,3,\dots ,|V(G)|+|E(G)|\}$ such that $f(x)+f(xy)+f(y)$ is a constant for every edge $xy\in E(G)$. An edge-magic graph $G$ is said to be super if $f(V(G))=\{1,2,3,\dots ,|V(G)|\}$. Furthermore, the edge-magic deficiency of a graph $G$, denoted $\mu (G)$, is defined as the minimum nonnegative integer $n$ such that $G\cup n{K}_1$ is edge-magic. Similarly, the \emph{super edge-magic deficiency} of a graph $G$, denoted ${\mu }_s(G)$, is either the minimum nonnegative integer $n$ such that $G\cup n{K}_1$ is super edge-magic or $+\mathrm{\infty }$ if there exists no such integer $n$. In this paper, we investigate the (super) edge-magic deficiency of chain graphs. Based on these, we propose some open problems.

Given a large finite point set, $P\subset {\mathbb{R}}^2$, we obtain upper bounds on the number of triples of points that determine a given pair of dot products. That is, for any pair of nonzero real numbers, $(\alpha ,\beta )$, we bound the size of the set $$\{(p,q,r)\in P\times P\times P:p\cdot q=\alpha ,p\cdot r=\beta \}.$$

An explicit formula for the number of spanning trees of the lexi- cographic product GLH] of two arbitrary graphs G and H is deduced in terms of structure parameters of G and H. Some properties on the number of spanning trees of G[H] are revealed. Sharp lower and upper bounds for the number of spanning trees of lexicographic product of graphs are established. In particular, simple formulae for the number of spanning trees of the lexicographic product of some special graphs are derived, which extend some previously known results
in the literature.

For a graph $G$, the expression $G\stackrel{v}{\to }(a_1,\dots ,a_s)$ means that for any $s$-coloring of the vertices of $G$, there exists $i\in \{1,\dots ,s\}$ such that there is a monochromatic $a_i$-clique of color $i$. The vertex Folkman numbers

$$F_v(a_1,\dots ,a_s;m-1)=min\{|V(G)|:G\stackrel{v}{\to }(a_1,\dots ,a_s)\text{ and }{K}_{m-1}⊈G\}$$

are considered, where $m=\sum _{i=1}^s(a_i–1)+1$.

With the help of a computer, we show that $F_v(2,2,5;6)=16$, and then we prove

$$F_v(a_1,\dots ,a_s;m-1)=m+9,$$

if $max\{a_1,\dots ,a_s\}=5$.

We also obtain the bounds

$$m+9\le F_v(a_1,\dots ,a_s;m-1)\le m+10,$$

if $max\{a_1,\dots ,a_s\}=6$.

The diameter of a graph can be affected by the addition or the deletion of some edges. In [3], we have studied the diameter variability of the Cartesian product of graphs. In this paper, we discuss about two fundamental products, strong and lexicographic products of graphs, whose diameter increases (decreases) by the deletion (addition) of a single edge. The problems of minimality and maximality of the product graphs with respect to its diameter are also solved. These problems are motivated by the fact that these graph products are good interconnection networks.

The concept of the skew energy of a digraph was introduced by Adiga, Balakrishnan and So in 2010. An oriented graph $G^{\sigma }$ is a simple undirected graph $G$ with an orientation, which assigns to each edge a direction so that $G^{\sigma }$ becomes a directed graph. Then $G$ is called the underlying graph of $G^{\sigma }$. Let $S(G^{\sigma })$ be the skew-adjacency matrix of $G^{\sigma }$ and ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ denote all the eigenvalues of $S(G^{\sigma })$. The skew energy of $G^{\sigma }$ is defined as the sum of the absolute values of all eigenvalues of $S(G^{\sigma })$. Recently, Gong, Li and Xu determined all oriented graphs with minimal skew energy among all connected oriented graphs on $n$ vertices with $m$ ($n\le m\le 2(n-2)$) arcs. In this paper, we determine all oriented graphs with the second and the third minimal skew energy among all connected oriented graphs with $n$ vertices and $m$ ($n\le m<2(n-2)$) arcs. In particular, when the oriented graphs are unicyclic digraphs or bicyclic digraphs, the second and the third minimal skew energy is determined.

In this paper, according to the symmetric Lanczos algorithm and general Gauss-type quadrature rule, we give some lower bounds on the Resolvent Estrada index $E{E}_r(G)$ and the Resolvent energy $ER(G)$.

The chordal-($k,l$) sandwich and strongly chordal-($k,l$) sandwich problems were considered in recent work [8, 9] where classification of the complexities of the problems for all possible nonnegative integer values for $k,l$ was considered. We extend the classification in [8, 9] by presenting polynomial time algorithms for some cases that remained open; currently, very few graph sandwich problems are known to be solvable in polynomial time.

An odd open dominating set of a graph is a subset of the graph’s vertices with the property that the open neighborhood of each vertex in the graph contains an odd number of vertices in the subset. An odd closed $r$-dominating set is a subset of the graph’s vertices with the property that the closed $r$-ball centered at each vertex in the graph contains an odd number of vertices in the subset.

We show that the $n$-fold direct product of simple graphs has an odd open dominating set if and only if each factor has an odd open dominating set. Secondly, we show that the $n$-fold strong product of simple graphs has an odd closed $r$-dominating set if and only if each factor has an odd closed $r$-dominating set.

Multireceiver authentication codes allow one sender to construct an authenticated message for a group of receivers such that each receiver can verify the authenticity of the received message. In this paper, we construct one multireceiver authentication code from pseudo-symplectic geometry over finite fields. The parameters and the probabilities of deceptions of the codes are also computed. The smaller the probability of successful attack, the higher the security of the authentication codes.

Ryser’s Conjecture states that for any $r$-partite $r$-uniform hypergraph, the vertex cover number is at most $r-1$ times the matching number. This conjecture is only known to be true for $r\le 3$. For intersecting hypergraphs, Ryser’s Conjecture reduces to saying that the edges of every $r$-partite intersecting hypergraph can be covered by $r-1$ vertices. This special case of the conjecture has only been proven for $r\le 5$.

It is interesting to study hypergraphs which are extremal in Ryser’s Conjecture, i.e., those hypergraphs for which the vertex cover number is exactly $r-1$ times the matching number. There are very few known constructions of such graphs. For large $r$, the only known constructions come from projective planes and exist only when $r-1$ is a prime power. Mansour, Song, and Yuster studied how few edges a hypergraph which is extremal for Ryser’s Conjecture can have. They defined $f(r)$ as the minimum integer so that there exists an $r$-partite intersecting hypergraph $\mathcal{H}$ with $\tau (\mathcal{H})=r-1$ and with $f(r)$ edges. They showed that $f(3)=3$, $f(4)=6$, $f(5)=9$, and $12\le f(6)\le 15$.

In this paper, we focus on the cases when $r=6,7$, and $11$. We show that $f(6)=13$, improving previous bounds. Also, by providing the first known extremal hypergraphs for the $r=7$ and $r=11$ case of Ryser’s Conjecture, we show that $f(7)\le 22$ and $f(11)\le 51$. Our results for $f(6)$ and $f(7)$ have been obtained independently by Aharoni, Barat, and Wanless.

Let $T=S\setminus (\cup \{A:A\text{ in }\mathcal{A}\})$, where $S$ is an orthogonal polytope in ${\mathbb{R}}^d$ for $d\ge 2$ and where $\mathcal{A}$ is a collection of $n$ pairwise disjoint open boxes contained in $S$. Point $x$ belongs to $\text{Ker }T$ if and only if $x$ belongs to $\text{Ker }S$ and no coordinate line at $x$ meets any $A$ in $\mathcal{A}$. In turn, this relationship between the staircase kernels of $S$ and $T$ produces a Krasnosel’skii-type result for $T$ in terms of $n$, extending the class of orthogonal polytopes for which such a theorem exists.

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to $K_{1,3}$. Let $k$ be an integer with $k\ge 2$. We prove that if $G$ is a claw-free graph of order at least $14k–13$ and with minimum degree at least four, then $G$ contains $k$ vertex-disjoint copies of $K_{1,4}$. This partially supports a conjecture proposed by Jiang, Chiba, Fujita and Yan.

A graph $G$ is said to be $k$-$\gamma$-edge critical if the domination number $\gamma (G)=k$ and $\gamma (G+uv)<k$ for every $uv\notin E(G)$. For the connected domination number ${\gamma }_c(G)=k$, the total domination number ${\gamma }_t(G)=k$ and the independent domination number $i(G)=k$, a $k$-${\gamma }_c$-edge critical graph, a $k$-${\gamma }_t$-edge critical graph and a $k$-$i$-edge critical graph are similarly defined. In our previous work, we proved that every $2$-connected $k$-${\gamma }_c$-edge critical graph is hamiltonian for $1\le k\le 3$ and we provided a class of $l$-connected $k$-${\gamma }_c$-edge critical non-hamiltonian graphs for $k\ge 4$ and $2\le l\le \frac{n-3}{k-1}$. The problem of interest is to determine a sufficient condition for $k$-${\gamma }_c$-edge critical graphs to be hamiltonian for $k\ge 4$. In this paper, we prove that every $2$-connected $4$-${\gamma }_c$-edge critical claw-free graph is hamiltonian. For $k\ge 5$, we provide a class of $k$-${\gamma }_c$-edge critical claw-free non-hamiltonian graphs of connectivity two. We further show that all $3$-connected $k$-${\gamma }_c$-edge critical claw-free graphs are hamiltonian for $1\le k\le 6$. Our methodology also establishes some results on the hamiltonian properties of $3$-connected $k$-$\mathcal{D}$-edge critical claw-free graphs where $\mathcal{D}\in \{\gamma ,{\gamma }_t,i\}$.

A star forest is a forest each of whose components is a star. The star arboricity of a graph $G$, denoted by $\text{st}(G)$, is the minimum number of star forests whose union covers all the edges of $G$. A nonzero element of a commutative ring $R$ with unity is said to be a $zero-divisor$ of $R$ if there exists a nonzero element $y\in R$ such that $xy=0$. Given a ring $R$ with unity, the $zero-divisorgraph$ of $R$, denoted by $\mathrm{\Gamma }(R)$, is the graph whose vertex set consists of the zero divisors of $R$ and two vertices $x,y\in V(\mathrm{\Gamma }(R))$ are adjacent if and only if $xy=0$ in $R$. This paper investigates the star arboricities of the zero divisor graphs $\mathrm{\Gamma }({\mathbb{Z}}_{p^n})$, where $n,p\in \mathbb{N}$ and $p$ is a prime. In particular, we give bounds for $\text{st}(\mathrm{\Gamma }({\mathbb{Z}}_{p^n}))$ when $n$ is odd and determine the values of $\text{st}(\mathrm{\Gamma }({\mathbb{Z}}_{p^n}))$ when $n$ is even.

An adjacent vertex distinguishing total coloring of a graph $G$ is a proper total $k$-coloring of $G$ such that any two adjacent vertices have different color sets, where the color set of a vertex $v$ contains the color of $v$ and the colors of its incident edges. Let ${\chi }_a^{”}(G)$ denote the smallest value $k$ in such a coloring of $G$. In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that if a planar graph $G$ with maximum degree $\mathrm{\Delta }\ge 9$ contains no $5$-cycles with more than one chord, then ${\chi }_a^{”}(G)\le \mathrm{\Delta }+3$.

The concept of the skew energy of a digraph was introduced by Adiga, Balakrishnan and $S_0$ in $2010$. Let $\overrightarrow{G}$ be an oriented graph of order $n$ and ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ denote all the eigenvalues of the skew-adjacency matrix of $\overrightarrow{G}$. The skew energy ${\epsilon }_s(\overrightarrow{G})=\sum _{i=1}^n|{\lambda }_i|$. Hou, Shen and Zhang determined the minimal and the second minimal skew energy of the oriented unicyclic graphs. In this paper, the oriented unicyclic graphs with the third, fourth and fifth minimal skew energy are characterized, respectively.