In this paper, we describe a backtrack search over parallel classes with a partial isomorph rejection to classify resolvable $2$-(12, 6, $5c$) designs. We use the intersection pattern between the parallel classes and the fact that any resolvable $2$-(12, 6, $5c$) design is also a resolvable $3$-(12, 6, $2c$) design to effectively guide the search. The method was able to enumerate all nonsimple resolutions and a subfamily of simple resolutions of a $2$-(12, 6, 15) design. The method is also used to confirm the computer classification of the resolvable $2$-(12, 6, $5c$) designs for $c\in \{1,2\}$. A consistency checking based on the principle of double counting is used to verify the computation results.

A restraint on a (finite undirected) graph $G=(V,E)$ is a function $r$ on $V$ such that $r(v)$ is a finite subset of $\mathbb{N}$; a proper vertex colouring $c$ of $G$ is permitted by $r$ if $c(v)\notin r(v)$ for all vertices $v$ of $G$ (we think of $r(v)$ as the set of colours forbidden at $v$). Given a large number of colors, for restraints $r$ with exactly one colour forbidden at each vertex the smallest number of colourings is permitted when $r$ is a constant function, but the problem of what restraints permit the largest number of colourings is more difficult. We determine such extremal restraints for complete graphs and trees.

Let $G$ be a graph with average degree greater than $k–2$. Erdős and Sós conjectured that $G$ contains every tree on $k$ vertices. A star is a tree consisting of one center vertex adjacent to all the other vertices, and a $double-broom$ is a tree made up of two stars and a path connecting the center of one star with the center of the other. If the path connecting the two stars has length 2 or 3, then $G$ contains the double-broom (unpublished). In this paper, we prove that $G$ contains every double-broom on $k$ vertices.

We indicate how to calculate the number of round-robin tournaments realizing a given score sequence. This is obtained by inductively calculating the number of tournaments realizing a score function. Tables up to 18 participants are obtained.

An urn contains $2n+1$ balls in two colors. The number of balls of a particular color is a random variable having binomial distribution with $p=\frac{1}{2}$. We sample the urn removing balls one by one without replacement. Our aim is to stop the process maximizing the probability that the color of the last selected ball is the minority color. We give an algorithm for an optimal stopping time, evaluate the probability of success and its asymptotic behavior.

The results of Laughlin and Johnson [1] are generalized in this paper, and open problems left at the end of [1] are addressed. New values of Anti-Waring numbers are given, including $N(2,4)$, $N(2,5)$, $N(2,6)$, and $N(2,7)$.

A function $f:V(G)\to \{0,1,2\}$ is a $Romandominatingfunction$ (or just RDF) if every vertex $u$ for which $f(u)=0$ is adjacent to at least one vertex $v$ 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 $Romandominationnumber$ of a graph $G$, denoted by ${\gamma }_R(G)$, is the minimum weight of a Roman dominating function on $G$. A graph $G$ is Roman domination critical upon edge subdivision if the Roman domination number increases whenever an edge is subdivided. In this paper, we study the Roman domination critical graphs upon edge subdivision. We present several properties, bounds, and general results for these graphs.

In [Discrete Math., 311 (2011), 688-689], Fujita defined $f(r,n)$ to be the maximum integer $k$ such that every $r$-edge-coloring of $K_n$ contains a monochromatic cycle of length at least $k$. In this paper, we investigate the values of $f(r,n)$ when $n$ is linear in $r$. We determine the value of $f(r,2r+2)$ for all $r\ge 1$ and show that $f(r,sr+c)=s+1$ if $r$ is sufficiently large compared with positive integers $s$ and $c$.

Given a labeling of the vertices and edges of a graph, we define a type of homogeneity that requires that the neighborhood of every vertex contains the same number of each of the labels. This homogeneity constraint is a generalization of regularity— all such graphs are regular. We consider a specific condition in which both the edge and vertex label sets have two elements and every neighborhood contains two of each label. We show that vertex homogeneity implies edge homogeneity (so long as the number of edges in any neighborhood is four), and give two theorems describing how to build new homogeneous graphs (or multigraphs) from others.

A red-blue coloring of a graph $G$ is an edge coloring of $G$ in which every edge of $G$ is colored red or blue. Let $F$ be a connected graph of size $2$ or more with a red-blue coloring, at least one edge of each color, where some blue edge of $F$ is designated as the root of $F$. Such an edge-colored graph $F$ is called a color frame. An $F$-coloring of a graph $G$ is a red-blue coloring of $G$ in which every blue edge of $G$ is the root edge of a copy of $F$ in $G$. The $F$-chromatic index ${\chi }_F^{\prime }(G)$ of $G$ is the minimum number of red edges in an $F$-coloring of $G$. A minimal $F$-coloring of $G$ is an $F$-coloring with the property that if any red edge of $G$ is re-colored blue, then the resulting red-blue coloring of $G$ is not an $F$-coloring of $G$. The maximum number of red edges in a minimal $F$-coloring of $G$ is the upper $F$-chromatic index ${\chi }_F”(G)$ of $G$. In this paper, we study the two color frames $Y_1$ and $Y_2$ that result from the claw $K_{1,3}$, where $Y_1$ has exactly one red edge and $Y_2$ has exactly two red edges. For a graph $G$, let ${\alpha }^{\prime }(G)$ and $\alpha ”(G)$ denote the matching number and lower matching number of $G$, respectively. It is shown that if $T$ is a tree of order at least $4$ having no vertex of degree $2$, then ${\chi }_{Y_1}^{\prime }(T)=\alpha ”(T)$ while ${\chi }_{Y_2}^{\prime }(T)\le 3\alpha ”(T)$ and this upper bound is sharp. For a color frame $F$ of a claw, sharp bounds are established for ${\chi }_F”(G)$ in terms of the matching number and a generalized matching parameter of a graph $G$. Other results and questions are also presented.

Let $H$ and $G$ be two simple graphs, where $G$ is a subgraph of $H$. A $G$-decomposition of $\lambda H$, denoted by $(\lambda H,G)$-GD, is a partition of all the edges of $\lambda H$ into subgraphs (G-blocks), each of which is isomorphic to $G$. A large set of $(\lambda H,G)$-GD, denoted by $(\lambda H,G)$-LGD, is a partition of all subgraphs isomorphic to $G$ of $H$ into $(\lambda H,G)$-GDs (called small sets). In this paper, we investigate the existence of $(\lambda K_{mn},K_{1,p})$-LGD and obtain some existence results, where $p\ge 3$ is a prime.

Let $M(b,n)$ be the complete multipartite graph with $b$ parts $B_0,\dots ,B_{b-1}$ of size $n$. A $z$-cycle system of $M(b,n)$ is said to be a $cycle-frame$ if the $z$-cycles can be partitioned into sets $S_1,\dots ,S_k$ such that for $1\le j\le k$, $S_j$ induces a $2$-factor of $M(b,n)\mathrm{\setminus }{B}_i$ for some $i\in {\mathbb{Z}}_b$. The existence of a $C_z$-frame of $M(b,n)$ has been settled when $z\in \{3,4,5,6\}$. Here, we completely settle the case of $C_z$-frames when $z$ is $8$, and we give some solutions for larger values of $z$.

A graph $G$ is said to be a $(2,k)$-regular graph if each vertex of $G$ is at a distance two away from $k$ vertices of $G$. A graph $G$ is called an $(r,2,k)$-regular graph if each vertex of $G$ is at a distance $1$ away from $r$ vertices of $G$ and each vertex of $G$ is at a distance $2$ away from $k$ vertices of $G$ \cite{9}. This paper suggests a method to construct a $((m+n–2),2,(m–1)(n–1))$-regular graph of smallest order $mn$ containing a given graph $G$ of order $n\ge 2$ as an induced subgraph for any $m>1$.

A broadcast on a graph $G$ is a function $f:V\to \{0,1,\dots ,\text{diam}G\}$ such that $f(v)<e(v)$ (the eccentricity of $v$) for all $v\in V$. The broadcast number of $G$ is the minimum value of $\sum _{v\in V}f(v)$ among all broadcasts $f$ for which each vertex of $G$ is within distance $f(v)$ from some vertex $v$ with $f(v)\ge 1$. This number is bounded above by the radius of $G$. A graph is uniquely radial if its only minimum broadcasts are broadcasts $f$ such that $f(v)=\text{rad}G$ for some central vertex $v$, and $f(u)=0$ if $u\ne v$. We characterize uniquely radial trees.

In this paper, we refer to a decomposition of a tripartite graph into paths of length $3$, or into $6$-cycles, as gregarious if each subgraph has at least one vertex in each of the three partite sets. For a tripartite graph to have a $6$-cycle decomposition it is straightforward to see that all three parts must have even size. Here we provide a gregarious decomposition of a complete tripartite graph $K(r,s,t)$ into paths of length $3$, and thus of $K(2r,2s,2t)$ into gregarious $6$-cycles, in all possible cases, when the straightforward necessary conditions on $r,s,t$ are satisfied.

For any graph $G=(V,E)$, a non-empty set $S\subseteq V$ is $secure$ if and only if $|N[X]\cap S|\ge |N[X]–S|$ for all $X\subseteq S$. The cardinality of a minimum secure set in $G$ is the security number of $G$. In this note, we give a new proof for the $securitynumber$ of grid-like graphs.

Let $G=(V,E)$ be a graph having at least $3$ vertices in each of its components. A set $L\subseteq V(G)$ is a liar’s dominating set if

1. $|N_G[v]\cap L|\ge 2$ for all $v\in V(G)$ and
2. $|(N_G[u]\cup N_G[v])\cap L|\ge 3$ for every pair $u,v\in V(G)$ of distinct vertices in $G$,

where $N_G[x]=\{y\in V\mid xy\in E\}\cup \{x\}$ is the closed neighborhood of $x$ in $G$. In this paper, we characterize the vertices that are contained in all or in no minimum liar’s dominating sets in trees. Given a tree $T$, we also propose a polynomial time algorithm to compute the set of all vertices which are contained in every minimum liar’s dominating set of $T$ and the set of all vertices which are not contained in any minimum liar’s dominating set of $T$.

A graph is chordal if and only if every cycle either has a chord or is a triangle. If an edge (or triangle) is defined to be a strength-$k$ edge (or triangle) whenever it is in at least $k$ maximum cliques, then a graph is strongly chordal if and only if, for every $k\ge 1$, every cycle of strength-$k$ edges either has a strength-$k$ chord or is a strength-$k$ triangle. Dual-chordal graphs have been defined so as to be the natural cycle/cutset duals of chordal graphs. A carefully crafted notion of dual strength allows a characterization of strongly dual-chordal graphs that is parallel to the above. This leads to a complete list of all $3$-connected strongly dual-chordal graphs.

An edge-coloured path is rainbow if the colours of its edges are distinct. For a positive integer $k$, an edge-colouring of a graph $G$ is rainbow $k$-connected if any two vertices of $G$ are connected by $k$ internally vertex-disjoint rainbow paths. The rainbow $k$-connection number $r{c}_k(G)$ is defined to be the minimum integer $t$ such that there exists an edge-colouring of $G$ with $t$ colours which is rainbow $k$-connected. We consider $r{c}_2(G)$ when $G$ has fixed vertex-connectivity. We also consider $r{c}_k(G)$ for large complete bipartite and multipartite graphs $G$ with equipartitions. Finally, we determine sharp threshold functions for the properties $r{c}_k(G)=2$ and $r{c}_k(G)=3$, where $G$ is a random graph. Related open problems are posed.

A Costas array of order $n$ is an $n\times n$ permutation matrix with the property that all of the $n(n-1)/2$ line segments between pairs of $1$’s differ in length or in slope. A Costas latin square of order $n$ is an $n\times n$ latin square where for each symbol $k$, with $1\le k\le n$, the cells containing $k$ determine a Costas array. The existence of a Costas latin square of side $n$ is equivalent to the existence of $n$ mutually disjoint Costas arrays. In 2012, Dinitz, Östergird, and Stinson enumerated all Costas latin squares of side $n\le 27$. In this brief note, a sequel to that paper, we extend this search to sides $n=28$ and $29$. In addition, we determine the sizes of maximal sets of disjoint Costas latin squares of side $n$ for $n\le 29$.

For a given graph $G$, the set of positive integers $v$ for which a $G$-design exists is usually called the spectrum for $G$ and the determination of the spectrum is sometimes called the spectrum problem. We consider the spectrum problem for $G$-designs satisfying additional conditions of balance, in the case where $G$ is a member of one of the following infinite families of trees: caterpillars, stars, comets, lobsters, and trees of diameter at most $5$. We determine the existence spectrum for balanced $G$-designs, degree-balanced and partially degree-balanced $G$-designs, and orbit-balanced $G$-designs. We also address the existence question for non-balanced $G$-designs, for $G$-designs which are either balanced or partially degree-balanced but not degree-balanced, and for $G$-designs which are degree-balanced but not orbit-balanced.