International Journal of Mathematics and Mathematical Sciences
Volume 5 (1982), Issue 3, Pages 553-564
doi:10.1155/S0161171282000520
Subsemi-Eulerian graphs
Charles Suffel1
, Ralph Tindell1
, Cynthia Hoffman3
and Manachem Mandell4
1Stevens Institute of Technology, Hoboken 07030, New Jersey, USA
3College of Saint Elizabeth, Convent Station 07961, New Jersey, USA
4Brooklyn College of the City, University of New York, Bedford Ave. and Ave. H, Brooklyn 11210, New York, USA
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.