Have a personal or library account? Click to login

Recognition of split-graphic sequences

Acta Universitatis Sapientiae, Informatica
Volume 6 (2014): Issue 2 (December 2014)
By:
Open Access
|Jan 2015

References

  1. [1] S. M. de Almeida, C. P. de Mello, A. Morgana, Classification problem for split graphs, J. Brazilian Comp. Soc., 18, (2) (2012) 95-101. ⇒266
    Search in Google Scholar
  2. [2] M. D. Barrus, Hereditary unigraphs and Erdős-Gallai equalities, Discrete Math., 313, (21) (2013) 2469-2481. ⇒263
    Search in Google Scholar
  3. [3] D. Bauer, S. L. Hakimi, E. Schmeichel, Recognising of tough graphs is NP-hard, Discrete Appl. Math., 28 (1995) 191-195. ⇒266
    Search in Google Scholar
  4. [4] C. Benzaken, P. L. Hammer, D. De Werra, Split graphs of Dilworth number 2, Discrete Math., 55, (2) (1985) 123-127. ⇒256
    Search in Google Scholar
  5. [5] Z. Blázsik, M. Hujter, A. Pluhár, Zs. Tuza, Graphs with no induced C4 and 2K2, Discrete Math., 115 (1993) 51-55. ⇒256, 263
    Search in Google Scholar
  6. [6] E. Boros, V. A. Gurvich, I. Zverovich, On split and almost CIS-graphs, Australas. J. Combin., 43 (2009) 163-180. ⇒255
    Search in Google Scholar
  7. [7] A. Brandst¨adt, Partitions of graphs into one or two stable sets and cliques, Discrete Math., 152 (1996) 47-54. ⇒254, 256
    Search in Google Scholar
  8. [8] A. Brandst¨adt, Corrigendum, Discrete Math., 186 (1998) 295-295. ⇒254, 256
    Search in Google Scholar
  9. [9] A. Brandst¨adt, P. L. Hammer, V. B. Le, V. V. Lozin, Bisplit graphs, Discrete Mathematics 299 (2005) 11-32. ⇒255, 25610.1016/j.disc.2004.08.046
    Search in Google Scholar
  10. [10] A. Brandst¨adt, V. B. Le, J. P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PL, 1999. ⇒254, 256, 266
    Search in Google Scholar
  11. [11] R. E. Burkard, P. L. Hammer, A note on Hamiltonian split graphs, J. Comb. Graph Theory, Series B, 28 (1980) 245-248. ⇒26510.1016/0095-8956(80)90069-6
    Search in Google Scholar
  12. [12] G. Chartrand, L. Lesniak, P. Zhang, Graphs and Digraphs, CRC Press, Boca Raton, FL, 2011. ⇒25310.1201/b14892
    Search in Google Scholar
  13. [13] V. Chungphaisan, Conditions for a sequences to be r-graphic, Discrete Math., 7 (1974) 31-39. ⇒257, 25810.1016/S0012-365X(74)80016-6
    Search in Google Scholar
  14. [14] V. Chvátal, The toughness of graphs, Discrete Math., 5 (1973) 215-228. ⇒26610.1016/0012-365X(73)90138-6
    Search in Google Scholar
  15. [15] R. J. Clarke, Covering a set by subsets, Discrete Math., 181 (1990) 147-152. ⇒ 26410.1016/0012-365X(90)90146-9
    Search in Google Scholar
  16. [16] 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. ⇒275
    Search in Google Scholar
  17. [17] P. Erdős, T. Gallai, Gráfok előírt fok´u pontokkal (Graphs with given degrees of vertices), Mat. Lapok, 11 (1960), 264-274. ⇒253, 256, 258, 280
    Search in Google Scholar
  18. [18] P. Erdős, A. Gyárfás, Split and balanced colorings of complete graphs, Discrete Mathematics, 200, (1-3) (1999), 79-86. ⇒264
    Search in Google Scholar
  19. [19] P. Erdős, M. S. Jacobson, J. Lehel, Graphs realizing the same degree sequences and their respective clique numbers, in: Y. Alavi (Ed.), Graph Theory, Combinatorics and Applications, vol. 1, John Wiley and Sons, New York, 1991, 439-449. ⇒264
    Search in Google Scholar
  20. [20] T. Feder, P. Hell, S. Klein, R. Motwani, List partitions, SIAM J. Discrete Math, 16 (2003) 449-478. ⇒278
    Search in Google Scholar
  21. [21] S. Földes, P. Hammer, Split graphs having Dilworth number two, Canad. J. Math. 29, (3) (1977) 666-672. ⇒254, 25610.4153/CJM-1977-069-1
    Search in Google Scholar
  22. [22] S. Földes, P. Hammer, Split graphs, in (ed. E. Hoffman et al.) Proc. 8th South- Eastern Conf. Combinatorics, Graph Theory Comp. Congressus Num., XIX (1977) 311-315. ⇒254, 256, 263
    Search in Google Scholar
  23. [23] S. Földes, P. Hammer, The Dilworth number of a graph, Annals Discrete Math., 2 (1978) 211-219. ⇒25610.1016/S0167-5060(08)70334-0
    Search in Google Scholar
  24. [24] D. R. Fulkerson, A. J. Hoffman, M. H. McAndrew, Some properties of graphs with multiple edges, Canad. J. Math., 17 (1965) 166-177. ⇒253, 269, 27110.4153/CJM-1965-016-2
    Search in Google Scholar
  25. [25] V. Gasharov, The Erdős-Gallai criterion and symmetric functions, Europ. J. Combinatorics, 18 (1997) 287-294. ⇒25810.1006/eujc.1996.0096
    Search in Google Scholar
  26. [26] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980. ⇒254, 256, 263, 27810.1016/B978-0-12-289260-8.50019-4
    Search in Google Scholar
  27. [27] R. J. Gould, M. S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi (Ed.), Combinatorics, Graph Theory and Algorithms, vol. 1, New Issues Press, Kalamazoo, Michigan, 1999, 451-460. ⇒261, 264
    Search in Google Scholar
  28. [28] J. L. Gross, J. Yellen, P. Zhang. Handbook of Graph Theory, CRC Press, Boca Raton, FL, 2013. ⇒252, 253, 254, 25610.1201/b16132
    Search in Google Scholar
  29. [29] A. Gyárfás, J. Lehel, On-line and first fit colorings of graphs. J. Graph Theory, 12, (2) (1988) 217-227. ⇒264
    Search in Google Scholar
  30. [30] A. Gyárfás, Generalized split graphs and Ramsey numbers, J. Comb. Theory, Series A 81, (2) (1998) 255-261. ⇒255, 256
    Search in Google Scholar
  31. [31] M. Habib, A.Mamcarz, Colored modular and split decompositions of graphs with applications to trigraphs, in (ed. D. Kratsch and I. Todinca) Graph-Theoretic Concepts in Computer Science (40th International Workshop, WG 2014, Nouanle- Fuzelier, France, June 25-27, 2014). Series: Lecture Notes in Computer Science, 8747, Springer Verlag, Berlin, 2014, 263-274. ⇒26610.1007/978-3-319-12340-0_22
    Search in Google Scholar
  32. [32] 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. ⇒257, 25810.1137/0110037
    Search in Google Scholar
  33. [33] S. L. Hakimi, E. F. Schmeichel, Graphs and their degree sequences: A survey, in: Theory and Applications of Graphs, Lecture Notes in Math. 642, Springer- Verlag, Berlin 1978, 225-235. ⇒26110.1007/BFb0070380
    Search in Google Scholar
  34. [34] P. L. Hammer, B. Simeone, The splittance of a graph, Combinatorica, 1, (3) (1981) 275-284. ⇒263, 264, 27810.1007/BF02579333
    Search in Google Scholar
  35. [35] P. Hanion, Enumeration of graphs by degree sequence, J. Graph Theory, 3 (1979) 295-299. ⇒26010.1002/jgt.3190030313
    Search in Google Scholar
  36. [36] V. Havel, A remark on the existence of finite graphs (Czech), ˘ Casopis P˘est. Mat., 80 (1955), 477-480. ⇒257, 258
    Search in Google Scholar
  37. [37] P. Heggerness, D. Kratsch, Linear-time certifying algorithms for recognizing split graphs and related graph classes, Nordic J. Comp., 14 (2007) 87-108. ⇒278
    Search in Google Scholar
  38. [38] P. Heggernes, F. Mancini, Minimal split completions. Discrete Appl. Math., 157, (12) (2009) 2659-2669. ⇒266
    Search in Google Scholar
  39. [39] A. P. Heinz, Total number of split graphs (chordal + chordal complement) on n vertices. In: (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2014. ⇒265
    Search in Google Scholar
  40. [40] P. Hell, D. Kirkpatrick, Linear-time certifying algorithms for near-graphical sequences, Discrete Math., 309, (18) (2009) 5703-5713. ⇒260
    Search in Google Scholar
  41. [41] P. Hell, S. Klein, F. Protti, L. Tito, On generalized split graphs, Electronic Notes Disc. Math., 7 (2001) 98-101. ⇒25510.1016/S1571-0653(04)00234-3
    Search in Google Scholar
  42. [42] L. Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, ACM Trans. Algorithms, 4(4), (2008), Art. 40, 20 pages. ⇒26610.1145/1383369.1383371
    Search in Google Scholar
  43. [43] A. Iványi, Reconstruction of complete interval tournaments, Acta Univ. Sapientiae, Inform., 1, (1) (2009) 71-88. ⇒252, 253, 256
    Search in Google Scholar
  44. [44] A. Iványi, Reconstruction of complete interval tournaments II, Acta Univ. Sapientiae, Math., 2, (1) (2010) 47-71. ⇒252, 253
    Search in Google Scholar
  45. [45] A. Iványi, Degree sequences of multigraphs, Annales Univ. Sci. Budapest., Rolando Eötvös Nom., Sectio Comp., 37 (2012) 195-214. ⇒ 256, 259, 260, 262
    Search in Google Scholar
  46. [46] A. Iványi, Z. Kása, Parallel enumeration of graphical sequences (in Hungarian), Alk. Mat. Lapok, 31, (2014) 1-58. ⇒260
    Search in Google Scholar
  47. [47] A. Iványi, L. Lucz, Degree sequences of multigraphs (in Hungarian), Alk. Mat. Lapok, 29, (2012) 1-54. ⇒260
    Search in Google Scholar
  48. [48] A. Iványi, L. Lucz, T. F. M´ori, P. S´ot´er, On the Erdős-Gallai and Havel-Hakimi algorithms. Acta Univ. Sapientiae, Inform. 3, 2 (2011) 230-268. ⇒ 256, 259, 260, 262, 275
    Search in Google Scholar
  49. [49] A. Iványi, S. Pirzada. Comparison based ranking, in: ed. A. Iványi, Algorithms of Informatics, Vol. 3, mondAt, Vác, 2013, 1209-1258. ⇒260
    Search in Google Scholar
  50. [50] A. E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size. In: Y. Alavi et. al. (eds.) Combinatorics, Graph Theory, and Algorithms, vol. 2., Michigan, New Issues Press, Kalamazoo, 1999, 535-544. ⇒260
    Search in Google Scholar
  51. [51] D. J. Kleitman, D. L. Wang, Algorithm for constructing graphs and digraphs with given valences and factors, Discrete Math., 6 (1973) 79-88. ⇒254, 257, 25810.1016/0012-365X(73)90037-X
    Search in Google Scholar
  52. [52] D. Kratsch, R. M. McConnell, K. Mehlhorn, J. P. Spinrad, Certifying algorithms for recognizing interval graphs and permutation graphs, SIAM J. Comput., 36, (2) (2006) 326-353. ⇒26610.1137/S0097539703437855
    Search in Google Scholar
  53. [53] D. Kratsch, J. Lehel, H. Müller, Toughness, hamiltonicity and split graphs, Discrete Math., 150 (1996) 231-245. ⇒26610.1016/0012-365X(95)00190-8
    Search in Google Scholar
  54. [54] M. D. Lamar, Split digraphs, Discrete Math., 312, (7) (2012) 1314-1325. ⇒26610.1016/j.disc.2011.12.023
    Search in Google Scholar
  55. [55] V. B. Le, H. N. de Ridder, Probe split graphs, Discrete Math. Theor. Comput. Sci., 9(1), (2007) 207-238. ⇒25510.46298/dmtcs.401
    Search in Google Scholar
  56. [56] J. S. Li, Z. X. Song, An extremal problem on the potentially pk-graphic sequence, Discrete Math., 212 (2000) 223-231. ⇒264
    Search in Google Scholar
  57. [57] J. S. Li, Z. X. Song, R. Luo, The Erdős-Jacobson-Lehel conjecture on potentially pk-graphic sequences is true, Sci. China Ser. A, 41 (1998) 510-520. ⇒264
    Search in Google Scholar
  58. [58] F. Maffray, M. Preissmann, Linear recognition of pseudo-split graphs, Discrete Appl. Math. 52 (1994) 307-312. ⇒263, 27910.1016/0166-218X(94)00022-0
    Search in Google Scholar
  59. [59] R. M. McConnell, K. Mehlhorn, S. Näher, P. Schweitzer, Certifying algorithms, Computer Science Review, 5, (2) (2011) 119-161. ⇒260
    Search in Google Scholar
  60. [60] C. McCreesh, Multi-threaded maximum clique, level 4 Project, School of Computing Science, of Glasgow University, 2013, 38 pages. ⇒264
    Search in Google Scholar
  61. [61] F. R. McMorris, C. Wang, P. Zhang, On probe interval graphs, Discrete Appl. Math., 88(1-3), (1998) 315-324. ⇒255
    Search in Google Scholar
  62. [62] S. D. Nikolopoulos, Constant-time parallel recognition of split graphs, Inf. Proc. Letters, 54, (1) (1995) 1-8. ⇒265
    Search in Google Scholar
  63. [63] P. M. Pardalos, J. Rappe, M. G. S. Resende, An exact parallel algorithm for the maximum clique problem, High Performance Algorithms and Software in Nonlinear Optimization, Applied Optimization, 24 (1998) 279-300. ⇒264
    Search in Google Scholar
  64. [64] P. M. Pardalos, J. Xue, The maximum clique problem, J. Global Opt. (1994) 301-328. ⇒264
    Search in Google Scholar
  65. [65] J. Peemüller, necessary conditions for hamiltonian split graphs, Discrete Math., 54 (1985) 45-57. ⇒265, 266
    Search in Google Scholar
  66. [66] S. Pirzada, An Introduction to Graph Theory, Universities Press, Orient Blackswan, India, 2012. ⇒253
    Search in Google Scholar
  67. [67] S. Pirzada, B. A. Chat, Potentially graphic sequences of split graphs, Kragujevac J. Math., 38, (1) (2014) 73-81. ⇒255, 256, 262, 263
    Search in Google Scholar
  68. [68] A. R. Rao, The clique number of a graph with given degree sequence, in: A. R. Rao (Ed.) Proc. Symp. on Graph Theory, MacMillan and Co. Limited, India, ISI Lecture Notes Series, 4 (1979) 251-267. ⇒260
    Search in Google Scholar
  69. [69] A. R. Rao, A survey of the theory of potentially P-graphic and forcibly P-graphic degree sequences, Comb. Graph Theory, Proc. Symp. (Calcutta 1980), Lect. Notes Math. 885 (1981) 417-440. ⇒26010.1007/BFb0092288
    Search in Google Scholar
  70. [70] A. R. Rao, An Erdős-Gallai type result on the clique number of a realization of a degree sequence (unpublished). ⇒260
    Search in Google Scholar
  71. [71] G. F. Royle, Counting set covers and split graphs, J. Integer Sequences, 3 (2000), Article 00.2.6, 5 pages. ⇒264
    Search in Google Scholar
  72. [72] M. C. Schmidt, N. F. Samatova, K. Thomas, B.-H. Park, A scalable, parallel algorithm for maximal clique enumeration, J. Parallel Dist. Comp., 69, (4) (2009) 417-428. ⇒264
    Search in Google Scholar
  73. [73] P. S. Segundo, D. Rodríguez-Losada, A. Jim´enez, An exact bit-parallel algorithm for the maximum clique problem, Computers & Operations Res., 38, (2) (2011) 571-581. ⇒264
    Search in Google Scholar
  74. [74] N. J. A. Sloane, The number of degree-vectors for simple graphs. In (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2014, http://oeis.org/A004251 . ⇒260
    Search in Google Scholar
  75. [75] S. Szabó, Parallel algorithms for finding cliques in a graph, J. Physics: Conf. Series, 268, (1) (2011) 012030. ⇒264
    Search in Google Scholar
  76. [76] E. Tomita, A. Tanaka, H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, 363, (1) (2006) 28-42. ⇒264
    Search in Google Scholar
  77. [77] A. Tripathi, H. Tyagi, A simple criterion on degree sequences of graphs. Discrete Appl. Math., 156, 18 (2008) 3513-3517. ⇒258
    Search in Google Scholar
  78. [78] A. Tripathi, S. Venugopalan, D. B. West, A short constructive proof of the Erdős-Gallai characterization of graphic lists, Discrete Math., 310, (4) (2010) 843-844. ⇒258
    Search in Google Scholar
  79. [79] R. I. Tyshkevich, The canonical decomposition of a graph, Doklady Akademii Nauk SSSR (in Russian), 24 (1980) 677-679. ⇒263
    Search in Google Scholar
  80. [80] R. I. Tyshkevich, A. A. Chernyak, Yet another method of enumerating unmarked combinatorial objects, Mathematical Notes, 48, (6) (1990) 1239-1245 and (in Russian) Mat. Zametki, 48, (6) (1990) 98-105. ⇒264
    Search in Google Scholar
  81. [81] R. I. Tyshkevich, O. I. Melnikow, V. M. Kotov, On graphs and degree sequences: the canonical decomposition (in Russian), Kibernetica, 6 (1981) 5-8. ⇒263
    Search in Google Scholar
  82. [82] Wikipedia, Split graph. http://en.wikipedia.org/wiki/Splitgraph, 2014. ⇒256, 263
    Search in Google Scholar
  83. [83] G. J. Woeginger, The taughness of split graphs, Discrete Math., 190 (1998) 195-197. ⇒266
    Search in Google Scholar
  84. [84] J.-H. Yin, Conditions for r-graphic sequences to be potentially K(r) m+1-graphic, Discrete Math., 309 (2009) 6271-6276. ⇒261
    Search in Google Scholar
  85. [85] J.-H. Yin, A generalization of a conjecture due to Erdős, Jacobson and Lehel, Discrete Math., 309 (2009) 2579-2583. ⇒261, 264
    Search in Google Scholar
  86. [86] J.-H. Yin, A Rao-type characterization for a sequence to have a realization containing a split graph, Discrete Math., 311 (2011) 2485-2489. ⇒255, 256
    Search in Google Scholar
  87. [87] J.-H. Yin, A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially Sr,s-graphic, Czechoslovak Math. J., 62, (3) (2012) 863-867. ⇒255, 256, 262, 279
    Search in Google Scholar
  88. [88] J.-H. Yin, An extension of A. R. Rao’s characterization of potentially Km+1- graphic sequences, Discrete Appl. Math., 161, (7-8) (2013) 1118-1127. ⇒256, 262
    Search in Google Scholar
  89. [89] J.-H. Yin, A Rao-type characterization for a sequence to have a realization containing an arbitrary subgraph H, Acta Math. Sin., 30, (3) (2014) 389-394. ⇒ 262
    Search in Google Scholar
  90. [90] J.-H. Yin, Y.-S. Li, Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size, Discrete Math., 209 (2005) 218-227. ⇒ 264
    Search in Google Scholar
  91. [91] B. Zavalnij, Three versions of clique search parallelization, J. Comp. Sci. Inf. Technology, 2(2), (2014) 9-20. ⇒264
    Search in Google Scholar
DOI: https://doi.org/10.1515/ausi-2015-0007 | Journal eISSN: 2066-7760
Journal RSS Feed
Language: English
Page range: 252 - 286
Submitted on: Jul 20, 2014
Published on: Jan 27, 2015
Published by: Sapientia Hungarian University of Transylvania
In partnership with: Paradigm Publishing Services
Publication frequency: 2 times per year
Keywords:
psplit graph,
jsplit graph,
bsplit graph,
graphic sequence,
linear time algorithm,
(a,
b,
n)-graph,
potentially split sequence
Related subjects:
Computer sciences,
Computer sciences, other

© 2015 Bilal A. Chat, Shariefudddin Pirzada, Antal Iványi, published by Sapientia Hungarian University of Transylvania
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Previous articleVolume 6 (2014): Issue 2 (December 2014)Next article