A set \(S\) of vertices in a graph \(G = (V, E)\) is a restrained dominating set of \(G\) if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V \setminus S\). The graph \(G\) is called restrained domination excellent if every vertex belongs to some minimum restrained dominating set of \(G\). We provide a characterization of restrained domination excellent trees.

In this paper, \(q\)-analogues of the Pascal matrix and the symmetric Pascal matrix are studied. It is shown that the \(q\)-Pascal matrix \(\mathcal{P}_n\) can be factorized by special matrices and the symmetric \(q\)-Pascal matrix \(\mathcal{Q}_n\) has the LDU-factorization and the Cholesky factorization. As byproducts, some \(q\)-binomial identities are produced by linear algebra. Furthermore, these matrices are generalized in one or two variables, where a short formula for all powers of \(q\)-Pascal functional matrix \(\mathcal{P}_n[x]\) is given. Finally, it is similar to Pascal functional matrix, we have the exponential form for \(q\)-Pascal functional matrix.

We view a lobster in this paper as below. A lobster with diameter at least five has a unique path \(H = x_0, x_1, \ldots, x_m\) with the property that, besides the adjacencies in \(H\), both \(x_0\) and \(x_m\) are adjacent to the centers of at least one \(K_{i,s}\), where \(s > 0\), and each \(x_i\), \(1 \leq i \leq m-1\), is at most adjacent to the centers of some \(K_{1,s}\), where \(s \geq 0\). This unique path \(H\) is called the central path of the lobster. We call \(K_{1,s}\) an even branch if \(s\) is nonzero even, an odd branch if \(s\) is odd, and a pendant branch if \(s = 0\). In this paper, we give graceful labelings to some new classes of lobsters with diameter at least five. In these lobsters, the degree of each vertex \(x_i\), \(0 \leq i \leq m-1\), is even and the degree of \(x_m\) may be odd or even, and we have one of the following features:

1. For some \(t_1, t_2, t_3\), \(0 \leq t_1 < t_2 < t_3 \leq m\), each \(x_i\), \(0 \leq i \leq t_1\), is attached to two types (odd and pendant), or all three types, of branches; each \(z_i\), \(t_1 + 1 \leq i \leq t_2\), is attached to all three types of branches; each \(x_i\), \(t_2 + 1 \leq i \leq t_3\), is attached to two types of branches; and if \(t_3 < m\) then each \(z_i\), \(t_3 + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.
2. For some \(t_1, t_2\), \(0 < t_1 < t_2 < m\), each \(x_i\), \(0 \leq i \leq t_1\), is attached to two types (odd and pendant), or all three types, of branches; each \(x_i\), \(t_1 + 1 \leq i \leq t_2\), is attached to two, or all three types of branches; and if \(t_2 < m\) then each \(x_i\), \(t_2 + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.
3. For some \(t\), \(0 \leq t \leq m\), each \(x_i\), \(0 \leq i \leq t\), is attached to all three types of branches; and if \(t < m\) then each \(x_i\), \(t + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.

In this paper, an algorithm for constructing self-centered graphs from trees and two more algorithms for constructing self-centered graphs from a given connected graph \(G\), by adding edges are discussed. Motivated by this, a new graph theoretic parameter \(sc_r(G)\), the minimum number of edges added to form a self-centered graph from \(G\) is defined. Bounds for this parameter are obtained and exact values of this parameter for several classes of graphs are also obtained.

A \((k;g)\)-graph is a \(k\)-regular graph with girth \(g\). A \((k;g)\)-cage is a \((k;g)\)-graph with the least number of vertices. In this note, we show that a \((k;g)\)-cage has an \(r\)-factor of girth at least \(g\) containing or avoiding a given edge for all \(r\), \(1 \leq r \leq k-1\).

This paper deals with the problem of constructing Hamiltonian paths of optimal weights in Halin graphs. There are three versions of the Hamiltonian path: none or one or two of end-vertices are specified. We present \(O(|V|)\) algorithms for all the versions of the problem.

It is widely recognized that certain graph-theoretic extremal questions play a major role in the study of communication network vulnerability. These extremal problems are special cases of questions concerning the realizability of graph invariants. We define a CS\((p, q, \lambda, \delta)\) graph as a connected, separable graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). In this notation, if the “CS” is omitted the graph is not necessarily connected and separable. An arbitrary quadruple of integers \((a, b, c, d)\) is called CS\((p, q, \lambda, \delta)\) realizable if there is a CS\((p, q, \lambda, \delta)\) graph with \(p = a\), \(q = b\), \(\lambda = c\) and \(\delta = d\). Necessary and sufficient conditions for a quadruple to be CS\((p, q, \lambda, \delta)\) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta)\), \((p, q, \lambda,\Delta )\), \((p, q, \delta, \Delta)\), \((p, q, \lambda, \delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\kappa\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.

An incidence graph of a given graph \(G\), denoted by \(I(G)\), has its own vertex set \(V(I(G)) = \{(ve) | v \in V(G), e \in E(G) \text{ and } v \text{ is incident to } e \text{ in } G\}\) such that the pair \(((ue)(vf))\) of vertices \((ue) (vf) \in V(I(G))\) is an edge of \(I(G)\) if and only if there exists at least one case of \(u = v, e = f, uv = e\) or \(uv = f\). In this paper, we carry out a constructive definition on incidence graphs, and investigate some properties of incidence graphs and some edge-colorings on several classes of them.

The maximum possible toughness among graphs with \(n\) vertices and \(m\) edges is considered for \(m \geq \lceil n^2/4 \rceil\). We thus extend results known for \(m \geq n\lfloor n/3 \rfloor\). When \(n\) is even, all of the values are determined. When \(n\) is odd, some values are determined, and the difficulties are discussed, leaving open questions.