In the classical book embedding problem, a $k$-book is defined to be a line $L$ in $3$-space (the spine) together with $k$ half-planes (the pages) joined together at $L$. We introduce two variations on the classical book in which edges are allowed to wrap in either one or two directions. The first is a cylindrical book where the spine is a line $L$ in $3$-space and the pages are nested cylindrical shells joined together at $L$. The second is a torus book where the spine is the inner equator of a torus and the pages are nested torus shells joined together at this equator. We give optimal edge bounds for embeddings of finite simple graphs in cylinder and torus books and give best-possible embeddings of $K_n$ in torus books. We also compare both books with the classical book.

We give necessary and sufficient conditions for the decomposition of the complete graphs with multiple holes, $K_n\setminus h{K}_v$, into the graph-pair of order $4$.

A vertex cover of a graph $G=(V,E)$ is a subset $S\subseteq V$ such that every edge is incident with at least one vertex in $S$, and $\alpha (G)$ is the cardinality of a smallest vertex cover. Let $\mathcal{T}$ be a collection of vertex covers, not necessarily minimum. We say $\mathcal{T}$ is closed if for every $S\in \mathcal{T}$ and every $e\in E$ there is a one-to-one function $f:S\to V$ such that (1) $f(S)$ is a vertex cover,(2) for some $s\in S$, $\{s,f(s)\}=e$, (3)for each $s$ in $S$, either $s=f(s)$ or $s$ is adjacent to $f(s)$, and (4) $f(S)\in \mathcal{T}$.A set is an eternal vertex cover if and only if it is a member of some closed family of vertex covers. The cardinality of a smallest eternal vertex cover is denoted ${\alpha }_m^{\mathrm{\infty }}(G)$. Eternal total vertex covers are defined similarly, with the restriction that the cover must also be a total dominating set. The cardinality of a smallest eternal total vertex cover is denoted ${\alpha }_{mt}^{\mathrm{\infty }}(G)$. These three vertex cover parameters satisfy the relation $\alpha (G)\le {\alpha }_m^{\mathrm{\infty }}(G)\le {\alpha }_{mt}^{\mathrm{\infty }}(G)\le 2\alpha (G).$ We define a triple $(p,q,r)$ of positive integers such that $p\le q\le r\le 2p$ to be feasible if there is a connected graph $G$ such that $\alpha (G)=p$, ${\alpha }_m^{\mathrm{\infty }}(G)=q$, and ${\alpha }_{mt}^{\mathrm{\infty }}(G)=r$. This paper shows all triples with the above restrictions are feasible if $p\ne q$ or $r\le \frac{3p}{2}$ and conjectures that there are no feasible triples of the form $(p,p,r)$ with $r>\frac{3p}{2}$. The graphs with triple $(p,p+1,2p)$ are characterized and issues related to the conjecture are discussed.

We study the area distribution of closed walks of length $n$, starting and ending at the origin. The concept of algebraic area of a walk in the square lattice is slightly modified and the usefulness of this concept is demonstrated through a simple argument. The idea of using a generating function of the form $(x+x^{-1}+y+y^{-1}{)}^n$ to study these walks is then discussed from a special viewpoint. Based on this, a polynomial time algorithm for calculating the exact distribution of such walks for a given length is concluded. The presented algorithm takes advantage of the Chinese remainder theorem to overcome the problem of arithmetic with large integers. Finally, the results of the implementation are given for $n=32,64,128$.

The Wiener polarity index of a graph $G$ is the number of unordered pairs of vertices $u,v$ such that the distance between $u$ and $v$ is three, which was introduced by Harold Wiener in 1947. A linear time algorithm for computing the Wiener polarity index of trees was described, and also an algorithm which computes the index $W_p(G)$ for any given connected graph $G$ on $n$ vertices in time $O(M(n))$ was presented, where $M(n)$ denotes the time necessary to multiply two $n\times n$ matrices of small integers (which is currently known to be $O(n^{2.376})$). In this paper, we establish one polynomial algorithm to calculate the value of the Wiener polarity index of a bipartite graph.

Rado numbers are closely related to Ramsey numbers, but pertaining to equations and integers instead of cliques within graphs. For every integer $m\ge 3$ and every integer $c$, let the 2-color Rado number $r(m,c)$ be the least integer, if it exists, such that for every 2-coloring of the set $\{1,2,\dots ,r(m,c)\}$ there exists a monochromatic solution to the equation $\sum _{i=1}^{m-1}{x}_i+c=x_m$ .The values of $r(m,c)$ have been determined previously for nonnegative values of $c$, as well as all values of $m$ and $c$ such that $-m+2<c<0$ and $c<-(m-1)(m-2)$. In this paper, we find $r(m,c)$ for the remaining values of $m$ and $c$.

This paper deals with the Orchard crossing number of some families of graphs which are based on cycles. These include disjoint cycles, cycles which share a vertex and cycles which share an edge. Specifically, we focus on the prism and ladder graphs.

Let $i(G)$ be the number of isolated vertices in graph $G$. The isolated toughness of $G$ is defined as $I(G)=+\mathrm{\infty }$ if $G$ is complete; $I(G)=\text{min}\{|S|/i(G-S):S\subseteq V(G),i(G-S)\ge 2\}$ otherwise. In this paper, we determine that $G$ is a fractional $(g,f,n)$-critical graph if $I(G)\ge \frac{b^2+bn–1}{a}$ if $b>a$; $I(G)\ge b+n$ if $a=b$.

Let $\mathcal{C}$ be a finite family of boxes in ${\mathbb{R}}^d$, $d\ge 3$, with $S=\cup \{C:C\in \mathcal{C}\}$ connected and $p\in S$. Assume that, for every geodesic chain $D$ of $\mathcal{C}$-boxes containing $p$, each coordinate projection $\pi (D)$ of $D$ is staircase starshaped with $\pi (p)\in \text{Ker}\pi (D)$. Then $S$ is staircase starshaped and $p\in \text{Ker}S$. For $n$ fixed, $1\le n\le d-2$, an analogous result holds for composites of $n$ coordinate projections of $D$ into $(d-n)$-dimensional flats.

Let $T(G)$ and $\text{bind}(G)$ be the tenacity and the binding number, respectively, of a graph $G$. The inequality $T(G)\ge \text{bind}(G)–1$ was derived by D. Moazzami in [11]. In this paper, we provide a stronger lower bound on $T(G)$ that is best possible when $\text{bind}(G)\ge 1$.

In this paper, we give a new look at Sears’ ${}_3{\varphi }_2$ transformation formula via a discrete random variable. This interpretation may provide a method to calculate ${}_3{\varphi }_2$ by Monte Carlo experiments.

Symmetry plays a fundamental role in the design of experiments. In particular, symmetries of factorial designs that preserve their statistical properties are exploited to find designs with the best statistical properties. By using a result proved by Rosenberg [1], the concept of the LP relaxation orthogonal array polytope is developed and studied. A complete characterization of the permutation symmetry group of this polytope is made. Also, this characterization is verified computationally for many cases. Finally, a proof is provided.

Let $R$ be a noncommutative ring with identity and $Z(R{)}^{\ast }$ be the non-zero zero-divisors of $R$. The directed zero-divisor graph $\mathrm{\Gamma }(R)$ of $R$ is a directed graph with vertex set $Z(R{)}^{\ast }$ and for distinct vertices $x$ and $y$ of $Z(R{)}^{\ast }$, there is a directed edge from $x$ to $y$ if and only if $xy=0$ in $R$. S.P. Redmond has proved that for a finite commutative ring $R$, if $\mathrm{\Gamma }(R)$ is not a star graph, then the domination number of the zero-divisor graph $\mathrm{\Gamma }(R)$ equals the number of distinct maximal ideals of $R$. In this paper, we prove that such a result is true for the noncommutative ring $M_2(\mathbb{F})$, where $\mathbb{F}$ is a finite field. Using this, we obtain a class of graphs for which all six fundamental domination parameters are equal.

Multilevel Hadamard matrices (MHMs), whose entries are integers as opposed to the traditional restriction to $\{\pm 1\}$, have been introduced as a way to construct multilevel zero-correlation zone sequences for use in approximately synchronized code division multiple access (AS-CDMA) systems. This paper provides a construction technique to produce $2^m\times 2^m$ MHMs whose $2^m$ alphabet entries form an arithmetic progression, up to sign. This construction improves upon existing constructions because it permits control over the spacing and overall span of the MHM entries. MHMs with such regular alphabets are a more direct generalization of traditional Hadamard matrices and are thus expected to be more useful in applications analogous to those of Hadamard matrices. This paper also introduces mixed-circulant MHMs which provide a certain advantage over known circulant MHMs of the same size.

MHMs over the Gaussian (complex) and Hamiltonian (quaternion) integers are introduced. Several constructions are provided, including a generalization of the arithmetic progression construction for MHMs over real integers. Other constructions utilize amicable pairs of MHMs and c-MHMs, which are introduced as natural generalizations of amicable orthogonal designs and c-Hadamard matrices, respectively. The constructions are evaluated against proposed criteria for interesting and useful MHMs over these generalized alphabets.

A family $\mathcal{G}$ of connected graphs is a family with constant metric dimension if $\text{dim}(G)$ is finite and does not depend upon the choice of $G$ in $\mathcal{G}$. In this paper, we show that the sunlet graphs, the rising sun graphs, and the co-rising sun graphs have constant metric dimension.

A sequence $\{a_i:1\le i\le k\}$ of integers is a weak Sidon sequence if the sums $a_i+a_j$ are all different for any $i<j$. Let $g(n)$ denote the maximum integer $k$ for which there exists a weak Sidon sequence $\{a_i:1\le i\le k\}$ such that $1\le a_1<\cdots <a_k\le n$. Let the weak Sidon number $G(k)=\text{min}\{n\mid g(n)=k\}$. In this note, $g(n)$ and $G(k)$ are studied, and $g(n)$ is computed for $n\le 172$, based on which the weak Sidon number $G(k)$ is determined for up to $k=17$.

In this paper, we show that there exist all admissible 4-GDDs of type $g^6{m}^1$ for $g\equiv 0(\mathrm{mod}6)$. For 4-GDDs of type $g^u{m}^1$, where $g$ is a multiple of 12, the most values of $m$ are determined. Particularly, all spectra of 4-GDDs of type $g^u{m}^1$ are attained, where $g$ is a multiple of 24 or 36. Furthermore, we show that all 4-GDDs of type $g^u{m}^1$ exist for $g=10,20,28,84$ with some possible exceptions.

Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. Erdős raised the problem of determining $f(n)$. Erdős conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})\ge c{n}^{1+\frac{1}{k}}$. Hajós conjectured that every simple even graph on $n$ vertices can be decomposed into at most $\frac{n}{2}$ cycles. We present the problems, conjectures related to these problems, and we summarize the known results. We do not think Hajós’ conjecture is true.

Mobile guards on the vertices of a graph are used to defend the graph against an infinite sequence of attacks on vertices. A guard must move from a neighboring vertex to an attacked vertex (we assume attacks happen only at vertices containing no guard). More than one guard is allowed to move in response to an attack. The $m$-eternal domination number is the minimum number of guards needed to defend the graph. We characterize the trees achieving several upper and lower bounds on the $m$-eternal domination number.

Introduced in 1947, the Wiener index (sum of distances between all pairs of vertices) is one of the most studied chemical indices. Extensive results regarding the extremal structure of the Wiener index exist in the literature. More recently, the Gamma index (also called the Terminal Wiener index) was introduced as the sum of all distances between pairs of leaves. It is known that these two indices coincide in their extremal structures and that a nice functional relation exists for $k$-ary trees but not in general. In this note, we consider two natural extensions of these concepts, namely the sum of all distances between internal vertices (the Spinal index) and the sum of all distances between internal vertices and leaves (the Bartlett index). We first provide a characterization of the extremal trees of the Spinal index under various constraints. Then, its relation with the Wiener index and Gamma index is studied. The functional relation for $k$-ary trees also implies a similar result on the Bartlett index.

For an $n$-connected graph $G$, the $n$-wide diameter $d_n(G)$ is the minimum integer $m$ such that for any two vertices $x$ and $y$ there are at least $n$ internally disjoint paths of length at most $m$ from $x$ to $y$. For a given integer $l$, a subset $S$ of $V(G)$ is called a $(l,n)$-dominating set of $G$ if for any vertex $x\in V(G)–S$ there are at least $n$ internally disjoint paths of length at most $l$ from $S$ to $x$. The minimum cardinality among all $(l,n)$-dominating sets of $G$ is called the $(l,n)$-domination number. In this paper, we obtain that the $(l,\omega )$-domination numbers of the circulant digraph $G(d^n;\{1,d,\dots ,d^{n-1}\})$ is equal to 2 for $1\le \omega \le n$ and $d_{\omega }(G)–(g(d,n)+\delta )\le l\le d_{\omega }(G)–1$, where $g(d,n)=\text{min}\{e\lceil \frac{n}{2}\rceil –e–2,(\lfloor \frac{n}{2}\rfloor +1)(e–1)–2\}$, $\delta =0$ for $1\le \omega \le n–1$ and $\delta =1$ for $\omega =n$.