It is proved that the total chromatic number of any series-parallel graphs of degree at least \(3\) is \(\Delta(G)+1\).

We show that, in any coloring of the edges of \(K_{36}\), with two colors, there exists a triangle in the first color or a monochromatic \(K_{10}-e\) (\(K_{10}\) with one edge removed) in the second color, and hence we obtain a bound on the corresponding Ramsey number, \(R(K_3, K_{10}-e) \leq 38\). The new lower bound of \(37\) for this number is established by a coloring of \(K_{36}\) avoiding triangles in the first color and \(K_{10}-e\) in the second color. This improves by one the best previously known lower and upper bounds. We also give the bounds for the next Ramsey number of this type, \(42 \leq R(K_3, K_{11}-e) \leq 47\).

A subset \(S\) of \(V(G)\) is called a dominating set if every vertex in \(V(G) – S\) is adjacent to some vertex in \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality taken over all dominating sets of \(G\). A dominating set \(S\) is called a tree dominating set if the induced subgraph \(\langle S\rangle\) is a tree. The tree domination number \(\gamma_{tr}(G)\) of \(G\) is the minimum cardinality taken over all minimal tree dominating sets of \(G\). In this paper, some exact values of tree domination number and some properties of tree domination are presented in Section [2]. Best possible bounds for the tree domination number, and graphs achieving these bounds are given in Section [3]. Relationships between the tree domination number and other domination invariants are explored in Section [4], and some open problems are given in Section [5].

If \(G\) is a tricyclic Hamiltonian graph of order \(n\) with maximum degree \(3\), then \(G\) has one of two forms, \(X(q,r,s,t)\) and \(Y(q,r,s,t)\), where \(q+r+s+t=n\). We find the graph \(G\) with maximal index by first identifying the graphs of each form having maximal index.

Let \(G = (V_1, V_2; E)\) be a bipartite graph with \(|V_1| = |V_2| = n \geq 2k\), where \(k\) is a positive integer. Let \(\sigma'(G) = \min\{d(u)+d(v): u\in V_1, v\in V_2, uv \not\in E(G)\}\). Suppose \(\sigma'(G) \geq 2k + 2\). In this paper, we will show that if \(n > 2k\), then \(G\) contains \(k\) independent cycles. If \(n = 2k\), then it contains \(k-1\) independent \(4\)-cycles and a \(4\)-path such that the path is independent of all the \(k-1\) \(4\)-cycles.

New results on the enumeration of noncrossing partitions with \(m\) fixed points are presented, using an enumeration polynomial \(P_m(x_1, x_2, \ldots, x_m)\). The double sequence of the coefficients \(a_{m,k}\) of each \(x^k_i\) in \(P_m\) is endowed with some important structural properties, which are used in order to determine the coefficient of each \(x^k_ix^l_j\) in \(P_m\).

This paper concerns a labeling problem of the plane graphs \(P_{a,b}\). We discuss the magic labeling of type \((1,1,1)\) and consecutive labeling of type \((1,1,1)\) of the graphs \(P_{a,b}\).

In this note, we prove that the largest non-contractible to \(K^p\) graph of order \(n\) with \(\lceil \frac{2n+3}{3} \rceil \leq p \leq n\) is the Turán’s graph \(T_{2p-n-1}(n)\). Furthermore, a new upper bound for this problem is determined.

If \(u\) and \(v\) are vertices of a graph, then \(d(u,v)\) denotes the distance from \(u\) to \(v\). Let \(S = \{v_1, v_2, \ldots, v_k\}\) be a set of vertices in a connected graph \(G\). For each \(v \in V(G)\), the \(k\)-vector \(c_S(v)\) is defined by \(c_S(v) = (d(v, v_1), d(v, v_2), \ldots, d(v, v_k))\). A dominating set \(S = \{v_1, v_2, \ldots, v_k\}\) in a connected graph \(G\) is a metric-locating-dominating set, or an MLD-set, if the \(k\)-vectors \(c_S(v)\) for \(v \in V(G)\) are distinct. The metric-location-domination number \(\gamma_M(G)\) of \(G\) is the minimum cardinality of an MLD-set in \(G\). We determine the metric-location-domination number of a tree in terms of its domination number. In particular, we show that \(\gamma(T) = \gamma_M(T)\) if and only if \(T\) contains no vertex that is adjacent to two or more end-vertices. We show that for a tree \(T\) the ratio \(\gamma_L(T)/\gamma_M(T)\) is bounded above by \(2\), where \(\gamma_L(G)\) is the location-domination number defined by Slater (Dominating and reference sets in graphs, J. Math. Phys. Sci. \(22 (1988), 445-455)\). We establish that if \(G\) is a connected graph of order \(n \geq 2\), then \(\gamma_M(G) = n-1\) if and only if \(G = K_{1,n-1}\) or \(G = K_n\). The connected graphs \(G\) of order \(n \geq 4\) for which \(\gamma_M(G) = n-2\) are characterized in terms of seven families of graphs.

The edges of a graph can be either directed or signed (\(2\)-colored) so as to make some of the even-length cycles of the underlying graph into alternating cycles. If a graph has a signing in which every even-length cycle is alternating, then it also has an orientation in which every even-length cycle is alternating, but not conversely. The existence of such an orientation or signing is closely related to the existence of an orientation in which every even-length cycle is a directed cycle.

We deal with the problem of labeling the vertices, edges, and faces of a plane graph in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face, and the weights of all \(s\)-sided faces constitute an arithmetic progression of difference \(d\). In this paper, we describe various antimagic labelings for the generalized Petersen graph \(P(n, 2)\). The paper concludes with a conjecture.

It was shown by Abrham that the number of pure Skolem sequences of order \(n\), \(n \equiv 0\) or \(1 \pmod{4}\), and the number of extended Skolem sequences of order \(n\), are both bounded below by \(2^{\left\lfloor \frac{n}{3} \right\rfloor}\). These results are extended to give similar lower bounds for the numbers of hooked Skolem sequences, split Skolem sequences, and split-hooked Skolem sequences.

Jin and Liu discovered an elegant formula for the number of rooted spanning forests in the complete bipartite graph \(K_{a_1,a_2}\), with \(b_1\) roots in the first vertex class and \(b_2\) roots in the second vertex class. We give a simple proof of their formula, and a generalization for complete \(m\)-partite graphs, using the multivariate Lagrange inverse.

Using a linear space on \(v\) points with all block sizes \(|B| \equiv 0\) or \(1 \pmod{3}\), Doyen and Wilson construct a Steiner triple system on \(2v+1\) points that embeds a Steiner triple system on \(2|B|+1\) points for each block \(B\). We generalise this result to show that if the linear space on \(v\) points is extendable in a suitable way, there is a Steiner quadruple system on \(2v+2\) points that embeds a Steiner quadruple system on \(2(|B|+1)\) points for each block \(B\).

A graph with a graceful labeling (an \(\alpha\)-labeling) is called a graceful (\(\lambda\)-graceful) graph. In this paper, six methods for constructing bigger graceful graphs from a given graceful graph or a set of given \(\lambda\)-graceful graphs are provided. Two of which generalize Koh and others’ Theorems in [2, 3].

Let \(B_2\) be the bananas surface arising from the torus by contracting two different meridians of the torus to a simple point each. It was proved in [8] that there is not a finite Kuratowski theorem for \(B_2\).

A graph is outer-bananas-surface if it can be embedded in \(B_2\) so that all its vertices lie on the same face. In this paper, we prove that the class of the outer-\(B_2\) graphs is closed under minors. In fact, we give the complete set of \(38\) minor-minimal non-outer-\(B_2\) graphs and we also characterize these graphs by a finite list of forbidden topological minors.

We also extend outer embeddings to other pseudosurfaces. The \(S\) pseudosurfaces treated are spheres joined by points in such a way that each sphere has two singular points. We give an excluded minor characterization of outer-\(S\) graphs and we also give an explicit and finite list of forbidden topological minors for these pseudosurfaces.

We show that several known theorems on graphs and digraphs are equivalent. The list of equivalent theorems include Kotzig’s result on graphs with unique \(1\)-factors, a lemma by Seymour and Giles, theorems on alternating cycles in edge-colored graphs, and a theorem on semicycles in digraphs.

We consider computational problems related to the quoted results; all these problems ask whether a given (di)graph contains a cycle satisfying certain properties which runs through \(p\) prescribed vertices. We show that all considered problems can be solved in polynomial time for \(p < 2\) but are NP-complete for \(p \geq 2\).

We define a new graph operation called “dissolve \(N(v)\) into \(v\)” where \(N(v)\) is the set of vertices adjacent to a vertex \(v\) and characterize odd cycles of length greater than \(5\) in terms of \(p\)-critical graphs using this operation. This enables us to re-phrase the Strong Perfect Graph Conjecture,

Gray and Ramsay [5] showed that for any \(s \geq (2t – 1)2^t\), a \(t-(v,k)\) trade of volume \(s\) exists. In this note we improve their bound and show that for \(t \geq 3\), a given \(k\), and \(s \geq (t – 2)2^t + 2^{t-1} + 2\), there exists a simple \(t-(v,k)\) trade of volume \(s\).

\[S_{(p,x)} = \sum\limits_{k=0}^{n} {\binom{n}{k}}^p x^k\]

where \(n \geq 0\).

Then it is well-known that \(S_n(1,x), S_2(2,1), S_n(3,1)\) and \(S_n(3,1)\) can be exhibited in closed form. The formula

\[S_{2n}{(3,-1)} = (-1)^n\binom{2n}{n}\binom{3n}{n}\]

was discovered by A. C. Dixon in \(1891\). L. Carlitz [Mathematics Magazine, Vol. \(32 (1958), 47-48]\) posed the formulas

\[S_n{(3,1)}= ((x^n))(1-x^2)^nP_n(\frac{1+x}{1-x})\]

and

\[S_n{(4,1)} = ((x^n))(1-x)^{2n}\{P_n(\frac{1+x}{1-x})\}\]

where \(((x^n))f(x)\) means the coefficient of \(x^n\) in the series expansion of \(f(x)\). We use Legendre polynomials to get the analogous formulas

\[S_n{(3,-1)} = ((x^n))(1_x)^{2n}\]

and

\[S_n{(5,1)} = ((x^n))(1_x)^{2n}P_n(\frac{1+x}{1-x}S_n(3,x)\]

We obtain some partial results for \(S_n(p,x)\) when \(p\) is arbitrary, and also give a new proof of Dixon’s formula.

A graph \(H\) of order \(n\) is said to be embeddable in a graph \(G\) of order \(n\), if \(G\) contains a spanning subgraph isomorphic to \(H\). It is well known that any non-star tree \(T\) of order \(n\) is embeddable in its complement (i.e. in \(K_n – E(T)\)). In the paper “Packing two copies of a tree into its fourth power” by Hamamache Kheddouci, Jean-Francois Saclé, and Mariusz Wodgniak, Discrete Mathematics 213 (2000), 169-178, it is proved that any non-star tree \(T\) is embeddable in \(T^4 – E(T)\). They asked whether every non-star tree \(T\) is embeddable in \(T^3 – E(T)\). In this paper, answering their question negatively, we show that there exist trees \(T\) such that \(T\) is not embeddable in \(T^3 – E(T)\).

The linear \(2\)-arboricity \(la_2(G)\) of a graph \(G\) is the least integer \(k\) such that \(G\) can be partitioned into \(k\) edge-disjoint forests, whose component trees are paths of length at most \(2\). We prove that \(la_2(G) \leq \lfloor \frac{\Delta(G) + 4}{2} \rfloor\) if \(G\) is an outerplanar graph with maximum degree \(\Delta(G)\).

A paired-dominating set of a graph \(G\) is a dominating set of vertices whose induced subgraph has a perfect matching. We characterize the trees having unique minimum paired-dominating sets.

Given two graphs \(G\) and \(H \subseteq G\), we consider edge-colorings of \(G\) in which every copy of \(H\) has at least two edges of the same color. Let \(f(G,H)\) be the maximum number of colors used in such a coloring of \(E(G)\). Erdős, Simonovits, and Sós determined the asymptotic behavior of \(f\) when \(G = K_n\), and \(H\) contains no edge \(e\) with \(\chi(H – e) \leq 2\). We study the function \(f(G, H)\) when \(G = K_n\), or \(K_{m,n}\), and \(H\) is \(K_{2,t}\).

This article provides some new methods of construction of two and three associate class Nested Partially Balanced Incomplete Block (NPBIB) designs. The methods are based on Latin-square association scheme, rectangular association scheme, and triangular association scheme. One method of constructing NPBIB designs has also been given by incorporating a set of new treatments in place of each treatment in a Nested Balanced Incomplete Block (NBIB) design. Exhaustive catalogues of NPBIB designs based on two and three class association schemes with \(v \leq 30\) and \(r \leq 15\) have also been prepared.

A set \(D\) of vertices in a graph \(G\) is a total dominating set if every vertex of \(G\) has at least one neighbor in \(D\). The minimum cardinality of a total dominating set of \(G\) is called the total domination number of \(G\), denoted by \(\gamma_t(G)\). A total dominating set of \(G\) with cardinality \(\gamma_t(G)\) is called a \(\gamma_t\)-set of \(G\). We characterize trees with unique \(\gamma_t\)-sets. Further, we prove that \(\gamma_t(G) \leq \frac{3}{5}n(G)\) for graphs with unique \(\gamma_t\)-sets, and we characterize all graphs with unique \(\gamma_t\)-sets where \(\gamma_t(G) = \frac{3}{5}n(G)\).

A word \(w = w_1w_2\ldots w_n\) avoids an adjacent pattern \(\tau\) iff \(w\) has no subsequence of adjacent letters having all the same pairwise comparisons as \(\tau\). In [12] and [13] the concept of words and permutations avoiding a single adjacent pattern was introduced. We investigate the probability that words and permutations of length \(n\) avoid two or three adjacent patterns.

We consider a variant of what is known as the discrete isoperimetric problem, namely the problem of minimising the size of the boundary of a family of subsets of a finite set. We use the technique of `shifting’ to provide an alternative proof of a result of Hart. This technique was introduced in the early \(1980s\) by Frankl and Füredi and gave alternative proofs of previously known classical results like the discrete isoperimetric problem itself and the Kruskal-Katona theorem. Hence our purpose is to bring Hart’s result into this general framework.

The domatic number of a graph \(G\) is the maximum number of dominating sets into which the vertex set of \(G\) can be partitioned.

We show that the domatic number of a random \(r\)-regular graph is almost surely at most \(r\), and that for \(3\)-regular random graphs, the domatic number is almost surely equal to \(3\).

We also give a lower bound on the domatic number of a graph in terms of order, minimum degree, and maximum degree. As a corollary, we obtain the result that the domatic number of an \(r\)-regular graph is at least \((r+1)/(3ln(r+1))\).

The concept of circular chromatic number of graphs was introduced by Vince \((1988)\). In this paper, we define the circular chromatic number of uniform hypergraphs and study their basic properties. We study the relationship between the circular chromatic number, chromatic number, and fractional chromatic number of uniform hypergraphs.

For a given Hadamard design \(D\) of order \(n\), we construct another Hadamard design \(D’\) of the same order, which is disjoint from \(D\).

The existence question for the family of \(4-(15,5,\lambda)\) designs has long been answered for all values of \(\lambda\) except \(\lambda = 2\). Here, we resolve this last undecided case and prove that \(4-(15, 5, 2)\) designs are constructible.

In this note, we prove that a graph is of class one if \(G\) can be embedded in a surface with positive characteristic and satisfies one of the following conditions:(i) \(\Delta(G) \geq 3\) and \(g(G)\)(the girth of \(G\)) \(\geq 8\) (ii) \(\Delta(G) \geq 4\) and \(g(G) \geq 5\)(iii) \(\Delta(G) \geq 5\) and \(g(G) \geq 4\).