Advanced Search

A set of vertices of a graph G is a total dominating set if each vertex of G is adjacent to a vertex in the set. The total domination number of a graph Υt (G) is the minimum size of a total dominating set. We provide a short proof of the result that Υt (G) ≤ 2/3n for connected graphs with n ≥ 3 and a short characterization of the extremal graphs.

A k-monocore graph is a graph which has its minimum degree and degeneracy both equal to k. Integer sequences that can be the degree sequence of some k-monocore graph are characterized as follows. A nonincreasing sequence of integers d0, . . . , dn is the degree sequence of some k-monocore graph G, 0 ≤ k ≤ n − 1, if and only if k ≤ di ≤ min {n − 1, k + n − i} and ⨊di = 2m, where m satisfies [...] ≤ m ≤ k ・ n − [...] .

A graph is k-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most k. These graphs were introduced by Lick and White in 1970 and have been studied in several subsequent papers. We present sharp bounds on the diameter of maximal k-degenerate graphs and characterize the extremal graphs for the upper bound. We present a simple characterization of the degree sequences of these graphs and consider related results. Considering edge coloring, we conjecture...

The $k$-core of a graph $G$, $C_k\left(G\right)$, is the maximal induced subgraph $H\subseteq G$ such that $\delta \left(G\right)\ge k$, if it exists. For $k>0$, the $k$-shell of a graph $G$ is the subgraph of $G$ induced by the edges contained in the $k$-core and not contained in the $(k+1)$-core. The core number of a vertex is the largest value for $k$ such that $v\in C_k\left(G\right)$, and the maximum core number of a graph, $\widehat{C}\left(G\right)$, is the maximum of the core numbers of the vertices of $G$. A graph $G$ is $k$-monocore if $\widehat{C}\left(G\right)=\delta \left(G\right)=k$. This paper discusses some basic results on the structure of $k$-cores and $k$-shells....