Geodesic
Existence of a Trade-Off Factorization of a Partially $4$-Homogeneous Graph
Matematičeskie zametki, Tome 89 (2011) no. 3, pp. 378-383.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{MZM_2011_89_3_a6,
     author = {A. M. Magomedov},
     title = {Existence of a {Trade-Off} {Factorization} of a {Partially} $4${-Homogeneous} {Graph}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {378--383},
     publisher = {mathdoc},
     volume = {89},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2011_89_3_a6/}
}
TY  - JOUR
AU  - A. M. Magomedov
TI  - Existence of a Trade-Off Factorization of a Partially $4$-Homogeneous Graph
JO  - Matematičeskie zametki
PY  - 2011
SP  - 378
EP  - 383
VL  - 89
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2011_89_3_a6/
LA  - ru
ID  - MZM_2011_89_3_a6
ER  - 
%0 Journal Article
%A A. M. Magomedov
%T Existence of a Trade-Off Factorization of a Partially $4$-Homogeneous Graph
%J Matematičeskie zametki
%D 2011
%P 378-383
%V 89
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2011_89_3_a6/
%G ru
%F MZM_2011_89_3_a6
A. M. Magomedov. Existence of a Trade-Off Factorization of a Partially $4$-Homogeneous Graph. Matematičeskie zametki, Tome 89 (2011) no. 3, pp. 378-383. http://geodesic.mathdoc.fr/item/MZM_2011_89_3_a6/

[1] V. N. Sachkov, Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, M., 1982 | MR | Zbl

[2] A. M. Magomedov, “Uplotnenie raspisaniya s direktivnym srokom, kratnym kolichestvu zanyatii kazhdogo prepodavatelya”, Matem. zametki, 85:1 (2009), 65–72 | MR | Zbl

[3] J. Petersen, “Die Theorie der regulären graphs”, Acta Math., 15:1 (1891), 193–220 | DOI | MR | Zbl

[4] A. M. Magomedov, “Razmeschenie nedelimykh $2$-slov v matritse kak zadacha faktorizatsii grafa”, Vestnik Dagestansk. nauchn. tsentra, 2006, no. 23, 5–14

[5] A. M. Magomedov, “K voprosu o rebernoi raskraske dvudolnogo grafa”, Diskret. matem., 21:2 (2009), 153–158 | MR