Distinctive power of the alliance polynomial has been studied in previous works. For instance, it has been proved that the empty, path, cycle, complete, complete without one edge, and star graphs are characterized by its alliance polynomial. Moreover, it has been proved that the family of alliance polynomials of regular graphs with small degree is a very
special one, since it does not contain alliance polynomials of graphs other than regular graphs with the same degree. In this work, we prove that the alliance polynomial also
determines the wheel graphs.

An ordered tree, also known as a plane tree or a planar tree, is defined recursively as having a root and an ordered set of subtrees. A $3$-zebra tree is an ordered tree where all edges connected to the root (called height $1$) are tricolored, as are all edges at odd height. The edges at even height are all black as usual.

In this paper, we show that the number of $3$-zebra trees with $n$ edges is equal to the number of Schröder paths with bicolored level steps.

A split graph is a graph whose vertices can be partitioned into a clique and an independent set. Most results in spectral graph theory do not address multigraph concerns. Exceptions are [2] and [4], but these papers present results involving a special class of underlying split graphs, threshold graphs, in which all pairs of nodes exhibit neighborhood nesting, and all multiple edges are confined to the clique.

We present formulas for the eigenvalues of some infinite families of regular split multigraphs in which all multiple edges occur between the clique nodes and cone nodes, with multiplicity of multiple edges $\mu >1$ fixed, and which have integer eigenvalues for the adjacency, Laplacian, and signless Laplacian matrices.

A rigid vertex is a vertex with a prescribed cyclic order of its incident edges. An embedding of a rigid vertex graph preserves such a cyclic order in the surface at every vertex. A cellular embedding of a graph has the complementary regions homeomorphic to open disks.

The genus range of a $4$-regular rigid vertex graph $\mathrm{\Gamma }$ is the set of genera of closed surfaces that $\mathrm{\Gamma }$ can be cellularly embedded into. Inspired by models of DNA rearrangements, we study the change in the genus range of a graph $\mathrm{\Gamma }$ after the insertion of subgraph structures that correspond to intertwining two edges. We show that such insertions can increase the genus at most by $2$ and decrease by at most $1$, regardless of the number of new vertices inserted.

The hypercube cut number $S(d)$ is the minimum number of hyperplanes in the $d$-dimensional Euclidean space ${\mathbb{R}}^d$ that slice all the edges of the $d$-cube. The problem was originally posed by P. O’Neil in 1971. B. Grünbaum, V. Klee, M. Saks, and Z. Füredi have raised the problem in various contexts.

The identity $S(d)=d$ has been well-known for $d\le 4$ since 1986. However, it was only until the year 2000 that Sohler and Ziegler obtained a computational proof for $S(5)=5$. Nevertheless, finding a short proof for the problem, independent of computer computations, remains a challenging task.

We present a short proof for the result presented by Emamy-Uribe-Tomassini in Hypercube 2002 based on Tomassini’s Thesis. The proof here is substantially shorter than the original proof of 60 pages.

Percolation models are infinite random graph models which have applications to phase transitions and critical phenomena. In the site percolation model, each vertex in an infinite graph $G$ is retained independently with probability $p$ and deleted otherwise. The percolation threshold is the critical probability $p_c(G)$ such that if $p>p_c(G)$, there is positive probability that the random subgraph induced by the retained vertices has an infinite connected component, while the probability that all of its components are finite is one if $p<p_c(G)$.

There are few lattice graphs for which the site percolation threshold is exactly known, and rigorous bounds for unsolved lattices are very imprecise. The substitution method for computing bounds for the more common class of bond percolation models must be modified to apply to site models. Some modifications will be illustrated with an application to the $(4,8^2)$ Archimedean lattice, which is a vertex-transitive tiling of the plane by squares and regular octagons. An improved upper bound, $p_c^{site}(4,8^2)<0.785661$, is obtained.

In a finite projective plane $\text{PG}(2,q)$, a set of $k$ points is called a $(k,n)$-arc if the following two properties hold:
1. Every line intersects it in at most $n$ points.
2. There exists a line which intersects it in exactly $n$ points.

We are interested in determining, for each $q$ and each $n$, the largest value of $k$ for which a $(k,n)$-arc exists in $\text{PG}(2,q)$. If possible, we would like to classify those arcs up to isomorphism. We look at the problem for $q=11$.

A cyclic triple, $(a,b,c)$, is defined to be the set $\{(a,b),(b,c),(c,a)\}$ of ordered pairs. A Mendelsohn triple system of order $v$, or MTS$(v)$, is a pair $(M,\beta )$, where $M$ is a set of $v$ points and $\beta$ is a collection of cyclic triples, each containing pairwise distinct points of $M$ such that every ordered pair of distinct points of $M$ exists in exactly one cyclic triple of $\beta$. An antiautomorphism of a Mendelsohn triple system $(M,\beta )$ is a permutation of $M$ which maps $\beta$ to ${\beta }^{-1}$, where ${\beta }^{-1}=\{(c,b,a)\mid (a,b,c)\in \beta \}$. Necessary conditions for the existence of an MTS$(v)$ admitting an antiautomorphism consisting of two cycles of lengths $M$ and $N$, where $1<M\le N$, have been shown, and for the cases of $N=M$ and $N=2M$, sufficiency has been shown. We show sufficiency for the cases in which $M=13$ and $N=78,390,$ and $702$.

The study of the generalized Fermat variety

$${\varphi }_j=\frac{x^j+y^j+z^j+(x+y+z{)}^j}{(x+y)(x+z)(y+z)}$$

defined over a finite field $L={\mathbb{F}}_q$, where $q=2^n$ for some positive integer $n$, plays an important role in the study of (APN) functions and exceptional APN functions. This study arose after a characterization by Rodier that relates these functions with the number of rational points of ${\varphi }_j=(x,y,z)$. The most studied cases are when $j=2^k+1$ and $j=2^{2k}–2^k+1$, the Gold and Kasami-Welch numbers. In this article, we make a claim about the decomposition of ${\varphi }_j$ into absolutely irreducible components. If these components intersect transversally at a particular point, then the corresponding Kasami-Welch polynomial is absolutely irreducible. This implies that the function is not exceptional APN, thus helping us make progress on the stated conjecture.

For $n\ge 1$, let $a_n$ count the number of strings $s_1{s}_2{s}_3\dots s_n$, where
(i) $s_1=0$;
(ii) $s_i\in \{0,1,2\}$ for $2\le i\le n$;
(iii) $|s_i–s_{i-1}|\le 1$ for $2\le i\le n$.

Then $a_1=1$, $a_2=2$, $a_3=5$, $a_4=12$, and $a_5=29$.

In general, for $n\ge 3$, $a_n=2a_{n-1}+a_{n-2}$, and $a_n$ equals $P_n$, the $n$th \emph{Pell} number.

For these $P_n$ strings of length $n$, we count
(i) The number of occurrences of each symbol $0,1,2$;
(ii) The number of times each symbol $0,1,2$ occurs in an even or odd position;
(iii) The number of levels, rises, and descents within the strings;
(iv) The number of runs that occur within the strings;
(v) The sum of all strings considered as base $3$ integers;
(vi) The number of inversions and coinversions within the strings; and
(vii) The sum of the major indices for the strings.