International Journal of Mathematics and Mathematical Sciences
Volume 5 (1982), Issue 3, Pages 553-564
doi:10.1155/S0161171282000520
Subsemi-Eulerian graphs
1Stevens Institute of Technology, Hoboken 07030, New Jersey, USA
2College of Saint Elizabeth, Convent Station 07961, New Jersey, USA
3Brooklyn College of the City, University of New York, Bedford Ave. and Ave. H, Brooklyn 11210, New York, USA
Received 9 September 1980
Copyright © 1982 Charles Suffel et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
A graph is subeulerian if it is spanned by an eulerian supergraph. Boesch, Suffel and Tindell have characterized the class of subeulerian graphs and determined the minimum number of additional lines required to make a subeulerian graph eulerian.
In this paper, we consider the related notion of a subsemi-eulerian graph, i.e. a graph which is spanned by a supergraph having an open trail containing all of its lines. The subsemi-eulerian graphs are characterized and formulas for the minimum number of required additional lines are given. Interrelationships between the two problems are stressed as well.