Class one graphs (Q1112066)

Let be \(G=(V,E)\) be a simple graph and its core B is defined to be the subgraph of G induced by the vertices of maximum degree. In the present paper are given conditions on B which are sufficient for G to be class 1. First is introduced an edge-queue of G which is a sequence of all edges \(e\in E(G)\) with certain properties. Then is shown (Proposition 1): If G has an edge-queue then G is class 1. To get the main result is defined a B-queue of a simple graph B; this is a maximal sequence \((u_ 1,...,u_ k)\), \(u\in V(B)\), and a sequence \((S_ 0,...,S_ k)\) of subsets of V(B) which satisfy certain conditions. By using Proposition 1 is proved (Theorem 2): Let G be a simple graph with core B. If \((S_ 0,...,S_ k)\) and \((u_ 1,...,u_ k)\) is a B-queue with \(S_ k=V(B)\) then G is class 1. Moreover there are still given two corollaries containing sufficient conditions on cores B so that any graph with such a core is class 1. Finally by using certain properties of B-queues of a graph B (Lemma 5) is described an efficient algorithm for deciding whether or not a particular graph is class 1.