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.