×

zbMATH — the first resource for mathematics

Tripartite graphs with given degree set. (English) Zbl 1317.05032
Summary: If \(k\geq 1\), then the global degree set of a k-partite graph \(G=(V_1,V_2,\dots, V_k,E)\) is the set of the distinct degrees of the vertices of \(G\), while if \(k\geq 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.
MSC:
05C07 Vertex degrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] T. S. Ahuja, A. Tripathi, On the order of a graph with a given degree set. J. Comb. Math. Comb. Comput., 57 (2006) 157-162. ⇒74 · Zbl 1110.05022
[2] G. Chartrand, H. Gavlas, F. Harary, M. Schultz, On signed degrees in signed graphs, Czechoslovak Math. J., 44, 4 (1994) 677-690. ⇒79 · Zbl 0837.05110
[3] G. Chartrand, R. J. Gould, S. F. Kapoor, Graphs with prescribed degree sets and girth, Periodica Math. Hung., 12, 4 (1981) 261-266. ⇒78, 99 · Zbl 0449.05038
[4] G. Chartrand, L. Lesniak, J. Roberts, Degree sets for digraphs, Periodica Math. Hung., 7, 1 (1976) 77-85. ⇒100, 101 · Zbl 0337.05114
[5] G. Chartrand, L. Lesniak, P. Zhang, Graphs & Digraphs, CRC Press, Boca Raton, 2011. ⇒72, 77
[6] A. A. Chernyak, Minimal graphs with a given degree set and girth (Russian), Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk,1988, 2 21-25, 123. ⇒78 · Zbl 0647.05033
[7] T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms (third edition), The MIT Press/McGraw Hill, Cambridge/New York, 2009. ⇒85 · Zbl 1187.68679
[8] Z. Dziechcińska-Halamoda, Z. Majcher, J. Michael, Z. Skupień, Extremum degree sets of irregular oriented graphs and pseudodigraphs, Discussiones Math. Graph Theory,, 26, 2 (2006) 317-333. ⇒101 · Zbl 1142.05325
[9] J. A. Ellis, M. Mate-Montero, H. Müller, Serial and parallel algorithms for (k, 2)-partite graphs, J. Parallel Dist. Comp., 22 (1994) 129-137. ⇒81 · Zbl 0824.68086
[10] P. Erdős, H. Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Martin-Luther-Univ. Halle-Wittenburg, Math.-Natur. Reihe, 12 (1963) 251-258. ⇒77 · Zbl 0116.15002
[11] J. L. Gross, J. Yellen, P. Zhang. Handbook of Graph Theory (second editionI, CRC Press, Boca Raton, FL, 2014. ⇒72 · Zbl 1278.05001
[12] M. Hager. On score sets for tournaments, Discrete Math., 58 (1986) 25-34. ⇒99, 100 · Zbl 0583.05029
[13] S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a simple graph. J. SIAM Appl. Math.10 (1962) 496-506. ⇒79 · Zbl 0109.16501
[14] S. L. Hakimi, On the degrees of the vertices of a graph, F. Franklin Institute,279, (4) (1965) 290-308. ⇒ · Zbl 0173.26404
[15] F. Harary, On the notion of balance of a signed graph, Michigan Math. J.2, 2 (1953), 143-146. ⇒78, 79 · Zbl 0056.42103
[16] F. Harary, The number of linear, directed, rooted and connected graphs, Trans. Amer. Math. Soc, 78, 2 (1955) 445-463. ⇒79 · Zbl 0065.16702
[17] F. Harary, E. Harzheim, The degree sets of connected infinite graphs. Fund. Math., 118, 3 (1983) 233-236. ⇒101 · Zbl 0532.04001
[18] A. Iványi, Reconstruction of score sets, Acta Univ. Sapientiae, Informatica, 6, 2 (2014) 210-229. ⇒99
[19] A. Iványi, J. Elek, Reconstruction of tournaments using the set of outdegrees (in Russian), Heuristic Algorithms and Distributed Computations, 1, 4 (2014) 46-70. ⇒99
[20] A. Iványi, J. Elek, Degree sets of tournaments, Studia Univ. Babeş-Bolyai, Informatica, 59 (2014) 150-164. ⇒99
[21] A. Iványi, L. Lucz, T. Matuszka, G. Gombos, Score sets in multitournaments, I. Mathematical results, Annales Univ. Sci. Budapest., Sectio Comp., 40 (2013) 307-320. ⇒99 · Zbl 1289.68059
[22] A. Iványi, B. M. Phong. On the unicity of the score sets of multitournaments, in: Fifth Conference on Mathematics and Computer Science (Debrecen, June 9-12, 2004), University of Debrecen, 2006, 10 pages. ⇒99
[23] A. Iványi, S. Pirzada, N. A. Shah, Imbalances of bipartite multitournaments, Annales Univ. Sci. Budapest., Sectio Comp., 37 (2012) 215-238. ⇒99 · Zbl 1249.05069
[24] S. F. Kapoor, L. Lesniak, Degree sets for triangle-free graphs. In Second Int. Conf. Comb. Math. (New York, 1978), pp. 320-330, Ann. New York Acad. Sci., 319, New York Acad. Sci., New York, 1979. ⇒80
[25] S. F. Kapoor, A. D. Polimeni, C. E. Wall, Degree sets for graphs, Fund. Math., 95, 3 (1977) 189-194. ⇒73, 80 · Zbl 0351.05129
[26] F. Kárteszi, Ciclici come risoluzionidi un certoproblema di minimo, Bol. Un. Mat. Ital., 15 (1960) 522-528, or Mat. Lapok, 11 (1960) 323-329 (in Hungarian). ⇒77
[27] M. A. Khan, Equal sum sequences and imbalance sets of tournaments, arXiv, arXiv:1402.2456v1 [math.CO] 11 Feb 2014. ⇒102
[28] S. Koukichi, H. Katsuhiro, Some remarks on degree sets for graphs. Rep. Fac. Sci. Kagoshima Univ. No. 32 (1999), 9-14. ⇒73 · Zbl 0946.05028
[29] P. Kumar, M. N. J. Sarma, S. Sawlani, On directed tree realization of degree sets, in: ed. by S. K. Ghost, T. Tokuyama, WALCOM 2013, Lecture Notes in Computer Sciemce, 7748, 2013, 274-285. ⇒80 · Zbl 1379.05028
[30] Y. Manoussakis, H. P. Patil, Bipartite graphs and their degree sets, Electron. Notes on Discrete Math., (Proceedings of the R. C. Bose Centenary Symposium on Discrete Mathematics and Applications,) 15 (2003) 125-125. ⇒75 · Zbl 1190.05051
[31] Y. Manoussakis, H. P. Patil, V. Sankar, Further results on degree sets for graphs, Mano I. J. M. S.,1, 2 (2001) 1-6. ⇒75
[32] Y. Manoussakis, H. P. Patil, V. Sankar, Further results on degree sets for graphs, AKCE J. Graphs Combin., 1, 2 (2004) 77-82. ⇒75 · Zbl 1065.05032
[33] Y. Manoussakis, H. P. Patil, On degree sets and the minimum orders in bipartite graphs, Discussiones Math. Graph Theory,34, 2 (2014) 383-390. ⇒81, 88 · Zbl 1290.05063
[34] C. M. Mynhardt, Degree sets of degree uniform graphs, Graphs Comb., 1 (1985) 183-190. ⇒78
[35] S. Osawa, Y. Sabata, Degree sequuences related to degree sets, Kokyuroki, 1744 (2011) 151-158. ⇒99
[36] V. Petrović. On bipartite score sets, Zbornik radova Prirodno-matematičkog Fakulteta Universitetr u Novom Sadu, Ser. Mat., 13 (1983) 297-303. ⇒102, 103
[37] S. Pirzada, An Introduction to Graph Theory, Universities Press, Hyderabad, India, 2012. ⇒73, 77, 99
[38] S. Pirzada, F. A. Dar, Signed degree sets in signed tripartite graphs, Matematicki Vesnik, 59, 3 (2007) 121-124. ⇒96, 97, 99 · Zbl 1224.05222
[39] S. Pirzada, F. A. Dar, A. Iványi, Existence of bipartite and tripartite graphs with prescribed degree sets, Heuristic Alg. Dist. Comp., 1, 1 (2015) 62-72. ⇒ 81
[40] S. Pirzada, A. Iványi, M. A. Khan. Score sets and kings, in ed. A. Iványi, Algorithms of Informatics, Vol. 3, mondAt, Vác, 2013, 1337-1389. ⇒ 99
[41] S. Pirzada, Merajuddin, T. A. Naikoo, Score sets in oriented 3-partite graphs, Analysis Theory Appl., 4 (2007) 363-374. ⇒103 · Zbl 1150.05017
[42] S. Pirzada, T. A. Naikoo, Score sets in oriented k-partite graphs, AKCE J. Graphs Combin., 3, 2 (2006) 135-145. ⇒103 · Zbl 1123.05045
[43] S. Pirzada, T. A. Naikoo, Score sets in k-partite tournaments, J. Appl. Math. Comp.22, 1-2 (2006) 237-245. ⇒101 · Zbl 1106.05043
[44] S. Pirzada, T. A. Naikoo, Score sets in oriented graphs, Appl. Anal. Discrete Math., 2, 1 (2008) 107-113. ⇒99, 102 · Zbl 1199.05155
[45] S. Pirzada, T. A. Naikoo, T. A. Chishti, Score sets in oriented bipartite graphs, Novi Sad J. Math, 36, 1 (2006) 35-45. ⇒101 · Zbl 1274.05198
[46] S. Pirzada, T. A. Naikoo, F. A. Dar, Signed degree sets in signed bipartite graphs, arXiv, arXiv/math0609129v1 [math.CO], 5 September 2006, 5 pages. ⇒87
[47] S. Pirzada, T. A. Naikoo, F. A. Dar, Signed degree sets in signed graphs, Czechoslovak Math. J., 57, 3 (2007) 843-848. ⇒79, 80 · Zbl 1174.05059
[48] S. Pirzada, T. A. Naikoo, F. A. Dar, Degree sets in bipartite and 3-partite graphs, Oriental J. Math. Sciences, 1, 1 (2007) 47-53. ⇒81, 91, 95 · Zbl 1144.05308
[49] S. Pirzada, T. A. Naikoo, F. A. Dar, A note on signed degree sets in signed bipartite graphs, Appl. Anal. Discrete Math., 2, 1 (2008) 114-117. ⇒87 · Zbl 1199.05159
[50] K. B. Reid. Score sets for tournaments, Congressus Numer., 21 (1978) 607-618. ⇒99, 100
[51] K. B. Reid. Tournaments: Scores, kings, generalizations and special topics, Congressus Numer., 115 (1996) 171-211. ⇒99 · Zbl 0899.05024
[52] T. A. Sipka, The orders of graphs with prescribed degree sets, J. Graph Theory, 4, 3 (1980) 301-307. ⇒74 · Zbl 0442.05058
[53] A. Tripathi, S. Vijay, On the least size of a graph with a given degree set, Discrete Appl. Math., 154 (2006) 2530-2536. ⇒75, 76 · Zbl 1110.05024
[54] A. Tripathi, S. Vijay, A short proof of a theorem on degree sets of graphs, Discrete Appl. Math., 155 (2007) 670-671. ⇒73 · Zbl 1113.05026
[55] R. I. Tyshkevich, A. A. Chernyak, Decomposition of graphs, Cybernetics Syst. Anal.21, (1985) 231-242. In Russian: Kibernetika, 2 (1985) 65-74. ⇒73 · Zbl 0605.05041
[56] R. I. Tyshkevich, A. A. Chernyak, Zh. A. Chernyak, Decomposition of graphs, I, Cybernetics Syst. Anal., 23, 6 (1987), 734-745. In Russian: Kibernetika, 6 (1987) 12-19. ⇒73 · Zbl 0656.05053
[57] R. I. Tyshkevich, A. A. Chernyak, Zh. A. Chernyak, Decomposition of graphs, II, Cybernetics Syst. Anal., 24, 2 (1988), 137-152. In Russian: Kibernetika, 2 (1988) 1-12. ⇒73 · Zbl 0712.05055
[58] R. I. Tyshkevich, A. A. Chernyak, Zh. A. Chernyak, Decomposition of graphs, III, Cybernetics Syst. Anal., 24, 5 (1988), 539-550. In Russian: Kibernetika, 5 (1988) 1-8. ⇒73 · Zbl 0747.05095
[59] L. Volkmann, Some remarks on degree sets of multigraphs, J. Combin. Math. Combin. Comput., 77 (2011) 45-49. ⇒76, 77 · Zbl 1233.05089
[60] K. Wayland, Bipartite score sets, Canadian Math. Bull., 26 (1983) 273-279. ⇒102, 103 · Zbl 0477.05037
[61] P. K. Wong, Cages—a survey, J. Graph Theory, 6, 1 (1982) 1-22. ⇒78
[62] Y. H. Yan, K. W. Lih, D. Kuo, G. J. Chang, Signed degree sequences in signed graphs, J. Graph Theory, 26, 1 (1977) 111-117. ⇒79 · Zbl 0890.05072
[63] T. X. Yao. On Reid conjecture of score sets for tournaments. Chinese Science Bull., 34 (1989) 804-808. ⇒99, 100 · Zbl 0687.05024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.