The minimum orders of degree-continuous graphs with prescribed degree sets were investigated by Gimbel and Zhang, Czechoslovak Math. J. 51 (126) (2001), 163–171. The minimum orders were not completely determined in some cases. In this note, the exact values of the minimum orders for these cases are obtained by giving improved upper bounds.
A graph G is called locally s-regular if the neighbourhood of each vertex of G nduces a subgraph of G which is regular of degree s. We study graphs which are locally s-regular and simultaneously regular of degree r.
Let $G$ be a simple graph. A subset $S \subseteq V$ is a dominating set of $G$, if for any vertex $v \in V~- S$ there exists a vertex $u \in S$ such that $uv \in E (G)$. The domination number, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set. In this paper we prove that if $G$ is a 4-regular graph with order $n$, then $\gamma (G) \le \frac{4}{11}n$.
Let $G$ be a connected simple graph on $n$ vertices. The Laplacian index of $G$, namely, the greatest Laplacian eigenvalue of $G$, is well known to be bounded above by $n$. In this paper, we give structural characterizations for graphs $G$ with the largest Laplacian index $n$. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on $n$ and $k$ for the existence of a $k$-regular graph $G$ of order $n$ with the largest Laplacian index $n$. We prove that for a graph $G$ of order $n \geq 3$ with the largest Laplacian index $n$, $G$ is Hamiltonian if $G$ is regular or its maximum vertex degree is $\triangle (G)=n/2$. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results.
For a finite group $G$, the intersection graph of $G$ which is denoted by $\Gamma(G)$ is an undirected graph such that its vertices are all nontrivial proper subgroups of $G$ and two distinct vertices $H$ and $K$ are adjacent when $H\cap K\neq1$. In this paper we classify all finite groups whose intersection graphs are regular. Also, we find some results on the intersection graphs of simple groups and finally we study the structure of
${\rm Aut}(\Gamma(G))$., Hossein Shahsavari, Behrooz Khosravi., and Obsahuje bibliografii
For any nontrivial connected graph $F$ and any graph $G$, the {\it $F$-degree} of a vertex $v$ in $G$ is the number of copies of $F$ in $G$ containing $v$. $G$ is called {\it $F$-continuous} if and only if the $F$-degrees of any two adjacent vertices in $G$ differ by at most 1; $G$ is {\it $F$-regular} if the $F$-degrees of all vertices in $G$ are the same. This paper classifies all $P_4$-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph $F$ other than the star $K_{1,k}$, $k \geq 1$, there exists a regular graph that is not $F$-continuous. If $F$ is 2-connected, then there exists a regular $F$-continuous graph that is not $F$-regular.
The signed total domination number of a graph is a certain variant of the domination number. If $v$ is a vertex of a graph $G$, then $N(v)$ is its oper neighbourhood, i.e. the set of all vertices adjacent to $v$ in $G$. A mapping $f: V(G) \rightarrow \lbrace -1, 1\rbrace $, where $V(G)$ is the vertex set of $G$, is called a signed total dominating function (STDF) on $G$, if $\sum _{x \in N(v)} f(x) \ge 1$ for each $v \in V(G)$. The minimum of values $\sum _{x \in V(G)} f(x)$, taken over all STDF’s of $G$, is called the signed total domination number of $G$ and denoted by $\gamma _{\mathrm st}(G)$. A theorem stating lower bounds for $\gamma _{\mathrm st}(G)$ is stated for the case of regular graphs. The values of this number are found for complete graphs, circuits, complete bipartite graphs and graphs on $n$-side prisms. At the end it is proved that $\gamma _{\mathrm st}(G)$ is not bounded from below in general.