The graph resulting from contracting edge $e$ is denoted $G/e$. An edge $e$ is radius-essential if $rad(G/e)<rad(G)$. Let $c_r(G)$ denote the number of radius-essential edges in graph $G$. In this paper, we study realizability questions relating to the number of radius-essential edges, give bounds on $c_r(G)$ in terms of radius and order, and we characterize various classes of graphs achieving extreme values of $c_r(G)$.

We prove tight estimates on the minimum weight of an edge decomposition of the complete graph into subgraphs of 3 or 4 edges, where the weight of a subgraph is the number of its vertices. We conjecture that the weighted edge decomposition problem on general graphs is NP-complete for every $k>2$. This conjecture is shown to be true for every $k\le 11$ except $k=8$. The problem is motivated by the traffic grooming problem for optical networks.

There are six distinct ways in which the vertices of a 4-cycle may be coloured with two colours, called \text{colouring types}. Let $C$ be the set of these colouring types and let $S$ be a non-empty subset of $C$. Suppose we colour the vertices of $K_v$ with two colours. If $D$ is a 4-cycle decomposition of $K_v$ such that the colouring type of each 4-cycle is in $S$, then $D$ is said to have a \emph{colouring of type} $S$. Furthermore, the colouring is said to be \emph{proper} if every colouring type in $S$ is represented in $D$. For all possible $S$ of size one, two or three, excluding three cases already settled, we completely settle the existence question for 4-cycle decompositions of $K_v$ with a colouring of type $S$.

For a solution $S$ of the $n$-queens problem, let $M(S)$ denote the maximum of the absolute values of the diagonal numbers of $S$, and let $m(S)$ denote the minimum of those absolute values. For $n\ge 4$, let $F(n)$ denote the minimum value of $M(S)$, and let $f(n)$ denote the maximum value of $m(S)$, as $S$ ranges over all solutions of the $n$-queens problem. Say that a solution $S$ is an $n$-\emph{champion} if $M(S)=F(n)$ and $m(S)=f(n)$.

Approximately linear bounds are given for $F(n)$ and $f(n)$, along with computational results and several constructions together providing evidence that the bounds are excellent. It is shown that, in the range $4\le n\le 24$, $n$-champions exist except for $n=11,16,21,22$.

Let $S$ be a stable set in a graph $G$, possibly $S=\mathrm{\varnothing }$. The subgraph $G–N[S]$, where $N[S]$ is the closed neighborhood of $S$, is called a \emph{co-stable subgraph} of $G$. We denote by $\text{CSub}(G)$ the set of all co-stable subgraphs of $G$. A class of graphs $\mathcal{P}$ is called \emph{co-hereditary} if $G\in \mathcal{P}$ implies $\text{CSub}(G)\subseteq \mathcal{P}$. Our result: If the set of all minimal forbidden co-stable subgraphs for a non-empty co-hereditary class $\mathcal{P}$ is finite, then Stable Set is an NP-complete problem within $\mathcal{P}$. Also, we prove that the decision problem of recognizing whether a graph has a fixed graph $H$ as a co-stable subgraph is NP-complete for each non-trivial graph $H$.

In this paper, we show the cordiality of the following families of graphs: (1) Pyramid graphs, (2) One point unions of plys,(3) One point unions of wheel related graphs, (4) Path unions of shells of different sizes, (5) Path unions of flags of different sizes.

Many different approaches exist in studying graphs with high connectivity and small diameter. We consider the effect of deleting vertices and edges from a graph while maintaining a small diameter. The following property is introduced: A graph $G$ has property $B_{d,i,j}$ if and only if after the removal of at most $i$ vertices and at most $j$ edges, the resulting graph has diameter at most $d$ and is not the trivial graph on one vertex. The central theme of this paper is to investigate the structure of graphs that have property $B_{d,i,j}$ and to investigate the structure that is needed to imply that a graph has property $B_{d,i,j}$. Lower bounds on minimum degree and connectivity that imply property $B_{d,i,j}$ for specific values of $d$ are found. These bounds are also shown to be sharp in all but one case.

An $m$-cycle system of order $v$, denoted by $mCS(v)$, is a decomposition of the complete graph $K_v$ into $m$-cycles. We discuss two types of large sets of $mCS(v)$ and construct examples of both types for $(m,v)=(4,9)$ and one type for $(m,v)=(6,9)$. These are the first large sets of cycle systems constructed with $m>3$, apart from the Hamiltonian cycle decompositions given in [2].

For two vertices $u$ and $v$ in a connected graph $G$, the detour distance $D(u,v)$ from $u$ to $v$ is defined as the length of a longest $u-v$ path in $G$. The detour eccentricity $e_D(v)$ of a vertex $v$ in $G$ is the maximum detour distance from $v$ to a vertex of $G$. The detour radius ${\text{rad}}_D(G)$ of $G$ is the minimum detour eccentricity among the vertices of $G$, while the detour diameter ${\text{diam}}_D(G)$ of $G$ is the maximum detour eccentricity among the vertices of $G$. It is shown that

$${\text{rad}}_D(G)<{\text{diam}}_D(G)<2{\text{rad}}_D(G)$$ for every connected graph $G$ and that every pair $a,b$ of positive integers with $a\le b\le 2a$ is realizable as the detour radius and detour diameter of some connected graph. The detour center of $G$ is the subgraph induced by those vertices of $G$ having detour eccentricity ${\text{rad}}_D(G)$. A connected graph $G$ is detour self-centered if $G$ is its own detour center. The detour periphery of $G$ is the subgraph induced by the vertices of $G$ having detour eccentricity ${\text{diam}}_D(G)$. It is shown that every graph is the detour center of some connected graph. Detour self-centered graphs are investigated. We present sufficient conditions for a graph to be the detour periphery of some connected graph. Several classes of graphs that are not the detour periphery of any connected graph are determined.

In recent work, Corteel and Lovejoy extensively studied overpartitions as a means of better understanding and interpreting various $q$-series identities. Our goal in this article is quite different. We wish to prove a number of arithmetic relations satisfied by the overpartition function. Employing elementary generating function dissection techniques, we will prove identities such as

$$\sum _{n\ge 0}\overline{p}(8n+7)q^n=64\frac{(q^2{)}_{\mathrm{\infty }}^{22}}{(q{)}_{\mathrm{\infty }}^{23}}$$

and congruences such as

$$\overline{p}(9n+6)\equiv 0(\mathrm{mod}8)$$

where $\overline{p}(n)$ denotes the number of overpartitions of $n$.

Let $G=(V,E)$ be a graph with $|V|=p$ and $|E|=q$. The graph $G$ is total edge-magic if there exists a bijection $f:V\cup E\to \{1,2,\dots ,p+q\}$ such that for all $e=(u,v)\in E$, $f(u)+f(e)+f(v)$ is constant throughout the graph. A total edge-magic graph is called super edge-magic if $f(V)=\{1,2,\dots ,p\}$. Lee and Kong conjectured that for any odd positive integer $r$, the union of any $r$ star graphs is super edge-magic. In this paper, we supply substantial new evidence to support this conjecture for the case $r=3$.

We show that $\mathbb{Z}$-cyclic ordered triplewhist and directed triplewhist tournaments on $p$ elements exist when $p\equiv 9(\mathrm{mod}16)$ is prime.

If $G=(V,E,F)$ is a finite connected plane graph on $|V|=p$ vertices, $|E|=q$ edges and $|F|=t$ faces, then $G$ is said to be $(a,d)$-face antimagic iff there exists a bijection $h:E\to \{1,2,\dots ,q\}$ and two positive integers $a$ and $d$ such that the induced mapping $g_h:F\to \mathbb{N}$, defined by $g_h(f)=\sum \{h(u,v):\text{edge }(u,v)\text{ surrounds the face }f\}$, is injective and has the image set $g_h(F)=\{a,a+d,\dots ,a+(t–1)d\}$. We deal with $(a,d)$-face antimagic labelings for a certain class of plane graphs.

We provide tables which summarize various aspects of the finite linear groups $\text{GL}(n,2)$, $n<7$, in their action upon the vector space $V_n=V(n,2)$ and upon the associated projective space $\text{PG}(n–1,2)$. It is intended that the tabulated results should be immediately accessible to finite geometers, and to all others (design theorists, coding theorists, \ldots) who have occasional need of these groups. In the case $n=4$ attention is also paid to the maximal subgroup $\mathrm{\Gamma }\text{L}(2,4)$. In the case $n=6$ the maximal subgroups $\mathrm{\Gamma }\text{L}(2,8)$ and $\mathrm{\Gamma }\text{L}(3,4)$ are treated, as are class aspects of the tensor product structure $V_6=V_2\otimes V_3$, and of the exterior product structure $V_6={\wedge }^2{V}_4$.

It is conjectured that any 2-regular graph $G$ with $n$ edges has a $\rho$-labeling (and thus divides $K_{2n+1}$ cyclically). In this note, we show that the conjecture holds when $G$ has at most two components.