Existence of a Trade-Off Factorization of a Partially $4$-Homogeneous Graph

A. M. Magomedov

Daghestan State University

Abstract: We consider a graph $G$ with $2\kappa$ vertices of degree $5$ and $\kappa$ vertices of degree $2$, all other vertices being of degree $4$. In connection with the timetable optimization problem, we study necessary and sufficient conditions for the existence of a factorization of $G$ into two skeleton subgraphs whose edge sets are disjoint and have the same cardinality and, for each vertex of the graph, the numbers of edges incident to this vertex in these subgraphs differ at most by unity.

Keywords: timetable optimization, partially homogeneous graph, skeleton subgraph, trade-off factorization, Petersen criterion, Eulerian graph.

UDC: 519.1

Received: 30.11.2007
Revised: 11.03.2010

DOI: 10.4213/mzm9047

 English version: Mathematical Notes, 2011, 89:3, 361–365

Bibliographic databases:

• 
• 
•