<abstract xmlns="http://www.w3.org/1999/xhtml">If <italic>k</italic> ≥ 1, then the <italic>global degree set</italic> of a k-partite graph <italic>G</italic> = (<italic>V</italic>1, <italic>V</italic>2, . . . , <italic>V</italic>k, <italic>E</italic>) is the set of the distinct degrees of the vertices of <italic>G</italic>, while if <italic>k</italic> ≥ 2, then the <italic>distributed degree set</italic> of <italic>G</italic> is the family of the <italic>k</italic> degree sets of the vertices of the parts of <italic>G</italic>. We propose algorithms to construct bipartite and tripartite graphs with prescribed global and distributed degree sets consisting from <italic>arbitrary</italic> nonnegative integers. We also present a review of the similar known results on digraphs.</abstract>

If k ≥ 1, then the global degree set of a k-partite graph G = (V1, V2, . . . , Vk, E) is the set of the distinct degrees of the vertices of G, while if k ≥ 2, then the distributed degree set of G is the family of the k degree sets of the vertices of the parts of G. We propose algorithms to construct bipartite and tripartite graphs with prescribed global and distributed degree sets consisting from arbitrary nonnegative integers. We also present a review of the similar known results on digraphs.

Tripartite graphs with given degree set

Eötvös Loránd University, Faculty of Informatics, Budapest, Hungary

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Tripartite graphs with given degree set"}

If k ≥ 1, then the global degree set of a k-partite graph G = (V1, V2, . . . , Vk, E) is the set of the distinct degrees of the vertices of G, while if k ≥ 2,...

Tripartite graphs with given degree set

Publié en ligne: 08 juin 2015

Pages: 72 - 106

Reçu: 08 mars 2015

DOI: https://doi.org/10.1515/ausi-2015-0013

© Antal Iványi et al.

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.