Let \(\Gamma\) be a \(d\)-bounded distance-regular graph with diameter \(d \geq 3\) and with geometric parameters \((d, b, \alpha)\). Pick \(x \in V(\Gamma)\), and let \(P(x)\) be the set of all subspaces containing \(x\). Suppose \(P(x, m)\) is the set of all subspaces in \(P(x)\) with diameter \(m\), where \(1 \leq m < d\). Define a graph \(\Gamma'\) whose vertex-set is \(P(x, m)\), and in which \(\Delta_1\) is adjacent to \(\Delta_2\) if and only if \(d(\Delta_1 \cap \Delta_2) = m – 1\). We prove that \(\Gamma'\) is a distance-regular graph and compute its intersection numbers.

Let \(G\) be a \(contraction-critical\) \(\kappa\)-connected graph. It is known (see Graphs and Combinatorics, \(7 (1991) 15-21\)) that the minimum degree of \(G\) is at most \(\lfloor \frac{5\kappa}{4} \rfloor – 1\). In this paper, we show that if \(G\) has at most one vertex of degree \(\kappa\), then either \(G\) has a pair of adjacent vertices such that each of them has degree at most \(\lfloor \frac{5\kappa}{4} \rfloor – 1\), or there is a vertex of degree \(\kappa\) whose neighborhood has a vertex of degree at most \(\lfloor \frac{4\kappa}{4} \rfloor – 1\). Moreover, if the minimum degree of \(G\) equals to \(\frac{5\kappa}{4} – 1\) (and thus \(\kappa = 0 \mod 4\)), Su showed that \(G\) has \(\kappa\) vertices of degree \(\frac{5\kappa}{4} – 1\), guessed that \(G\) has \(\frac{3\kappa}{2}\) such vertices (see Combinatorics Graph Theory Algorithms and Application (Yousef Alavi et. al Eds.),World Scientific, \(1993, 329-337\)). Here, we verify that this is true.

A simple Kirkman packing design \(SKPD(\{w, w+1\}, v)\) with index \(\lambda\) is a resolvable packing with distinct blocks and maximum possible number of parallel classes, each containing \(u =v-w \lfloor \frac{v}{w} \rfloor\) blocks of size \(w+1\) and \(\frac{v-u(w+1)}{w}\) blocks of size \(w\), such that each pair of distinct elements occurs in at most \(\lambda\) blocks. In this paper, we solve the spectrum of simple Kirkman packing designs \(SKPD(\{3, 4\}, v)\) with index \(2\) completely.

In this paper, we study the matrices related to the idempotent number and the number of planted forests with \(k\) components on the vertex set \([n]\). As a result, the factorizations of these two matrices are obtained. Furthermore, the discussion goes to the generalized case. Some identities and recurrences involving these two special sequences are also derived from the corresponding matrix representations.

A Roman dominating function on a graph \(G = (V, E)\) is a function \(f : V \rightarrow \{0, 1, 2\}\) satisfying the condition that 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) = \sum_{u \in V} f(u)\). The minimum weight of a Roman dominating function on a graph \(G\), denoted by \(\gamma_R(G)\), is called the Roman domination number of \(G\). In [E.J. Cockayne, P.A. Dreyer, Jr.,S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs,Discrete Math. \(278(2004) 11-22.]\), the authors stated a proposition which characterized trees which satisfy \(\gamma_R(T) = \gamma(T) + 2\), where \(\gamma(T)\) is the domination number of \(T\). The authors thought the proof of the proposition was rather technical and chose to omit its proof; however, the proposition is actually incorrect. In this paper, we will give a counterexample of this proposition and introduce the correct characterization of a tree \(T\) with \(\gamma_R(T) = \gamma(T) + 2\).

Let \(G\) be a graph on \(2n\) vertices with minimum degree \(r\). We show that there exists a two-coloring of the vertices of \(G\) with colors \(-1\) and \(+1\), such that all open neighborhoods contain more \(+1\)’s than \(-1\)’s, and altogether the number of \(+1\)’s does not exceed the number of \(-1\)’s by more than \(O(\frac{n}{\sqrt{n}})\).

The \(Problème \;des \;Ménages\) \((Married \;Couples \;Problem)\), introduced by E. Lucas in 1891, is a classical problem that asks for the number of ways to arrange \(n\) couples around a circular table, such that husbands and wives are in alternate places and no couple is seated together. In this paper, we present a new version of the Menage Problem that carries constraints consistent with Muslim culture.

Let \(G\) be a connected simple graph with girth \(g\) and minimal degree \(\delta \geq 3\). If \(G\) is not up-embeddable, then, when \(G\) is 1-edge connected,

\[\gamma_M(G) \geq \frac{D_1(\delta,g)-2}{2D_1(\delta,g)-1}\beta(G)+ \frac{D_1(\delta,g)+1}{2D_1(\delta,g)-1}.\]

When \(G\) is \(k\)(\(k = 2, 3\))-edge connected ,

\[\gamma_M(G) \geq \frac{D_k(\delta,g)-1}{2D_k(\delta,g)}\beta(G)+ \frac{D_k(\delta,g)+1}{2D_k(\delta,g)}.\]

The functions \(D_k(\delta, g)\) (\(k = 1, 2, 3\)) are increasing functions on \(\delta\) and \(g\).

In this paper, the authors discuss the values of a class of generalized Euler numbers and generalized Bernoulli numbers at rational points.

For two vertices \(u\) and \(v\) in a graph \(G = (V,E)\), the detour distance \(D(u,v)\) is the length of a longest \(u-v\) path in \(G\). A \(u-v\) path of length \(D(u,v)\) is called a \(u-v\) detour. A set \(S \subseteq V\) is called a weak edge detour set if every edge in \(G\) has both its ends in \(S\) or it lies on a detour joining a pair of vertices of \(S\). The weak edge detour number \(dn_w(G)\) of \(G\) is the minimum order of its weak edge detour sets and any weak edge detour set of order \(dn_w(G)\) is a weak edge detour basis of \(G\). Certain general properties of these concepts are studied. The weak edge detour numbers of certain classes of graphs are determined. Its relationship with the detour diameter is discussed and it is proved that for each triple \(D, k, p\) of integers with \(8 \leq k \leq p-D+1\) and \(D \geq 3\) there is a connected graph \(G\) of order \(p\) with detour diameter \(D\) and \(dn_w(G) = k\). It is also proved that for any three positive integers \(a, b, k\) with \(k \geq 3\) and \(a \leq b \leq 2a\), there is a connected graph \(G\) with detour radius \(a\), detour diameter \(b\) and \(dn_w(G) = k\). Graphs \(G\) with detour diameter \(D \leq 4\) are characterized for \(dn_w(G) = p-1\) and \(dn_w^+(G) = p-2\) and trees with these numbers are characterized. A weak edge detour set \(S\), no proper subset of which is a weak edge detour set, is a minimal weak edge detour set. The upper weak edge detour number \(dn_w^+(G)\) of a graph \(G\) is the maximum cardinality of a minimal weak edge detour set of \(G\). It is shown that for every pair \(a, b\) of integers with \(2 \leq a \leq b\), there is a connected graph \(G\) with \(dn_w(G) = a\) and \(dn_w^+(G) = b\).