On embedding degree sequences
Abstract
Assume that we are given two graphic sequences, $\pi_1$ and $\pi_2$. We consider conditions for $\pi_1$ and $\pi_2$ which guarantee that there exists a simple graph $G_2$ realizing $\pi_2$ such that $G_2$ is the subgraph of any simple graph $G_1$ that realizes $\pi_1$.References
bibitem{AS} N.~Alon, J.~Spencer. {it The probabilistic method.} Third edition, John Wiley & Sons,
Inc., 2008.
bibitem{chvatal} V.~Chv'atal and E.~Szemer'edi. On the {E}rd{H o}s--{S}tone {T}heorem.
{em Journal of the London Mathematical Society}, s2-23 (2):207--214, 1981.
bibitem{corradi} K.~Corr'adi and A.~Hajnal. On the maximal number of independent circuits in a graph. {em Acta Mathematica Academiae Scientiarum Hungaricae}, 14:423--439, 1963.
bibitem{wellsep} B.~Csaba. On embedding well-separable graphs. {em Discrete Mathematics}, 308(19):4322--4331, 2008.
bibitem{ferrara} J.~Diemunsch, M.~Ferrara, S.~Jahanbekam, and J.~Shook. Extremal theorems for degree sequence packing and the 2-color discrete tomography problem. {em {S}{I}{A}{M} Journal of Discrete Mathematics}, 29(4):2088--2099, 2015.
bibitem{dirac} G.~Dirac. Some theorems on abstract graphs. {em Proceedings of the London Mathematical Society}, s3-2(1):69--81, 1952.
bibitem{gale} D.~Gale. A theorem on flows in networks. {em Pacific Journal of Mathematics}, 7(2):1073--1082, 1957.
bibitem{KSSz97} J.~Koml'os, G.~S'ark"ozy, and E.~Szemer'edi. Blow-up lemma. {em Combinatorica}, 17:109--123, 1997.
bibitem{KSSz98} J.~Koml'os, G.~S'ark"ozy, and E.~Szemer'edi. An algorithmic version of the blow-up lemma. {em Random Structures and Algorithms}, 12:297--312, 1998.
bibitem{KS93} J.~Koml'os and M.~Simonovits. Szemer'edi's regularity lemma and its applications in graph theory. {em Combinatorics: Paul ErdH{o}s is eighty}, 2:295--352, 1993.
bibitem{lovasz} L.~Lov'asz. {em {C}ombinatorial problems and exercises}. Corrected reprint of the 1993 second edition,
AMS Chelsea Publishing, Providence, RI, 2007.
bibitem{Ryan} R.~Martin. The edit distance in graphs: Methods, results, and generalizations. In A.~Beveridge, J.~Griggs, L.~Hogben, G.~Musiker, and P.~Tetali, editors, {em Recent Trends in Combinatorics}, pages 31--62. Springer International Publishing, Cham, 2016.
bibitem{ryser} H.~Ryser. Combinatorial properties of matrices of zeros and ones.
{em Canadian Journal of Mathematics}, 9:371--377, 1957.
bibitem{sissokho} M.~Sahs, P.~Sissokho, and J.~Torf. A zero-sum theorem over $mathbb{Z}$. {em Integers}, 13:#A70, 2013.
bibitem{SZ} E.~Szemer'edi. Regular partitions of graphs. {em Colloques Internationaux C.N.R.S textbf{260} - Probl`emes Combinatoires et Th'eorie des Graphes}, pages 399--401, 1976.
bibitem{west} D.~West. {em Introduction to graph theory}. Prentice Hall, Second edition, 2001.
DOI:
https://doi.org/10.31449/inf.v43i1.2684Downloads
Published
How to Cite
Issue
Section
License
Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.
All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.
Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.
