Complexity of decomposing graphs into factors with given diameters or radii

Ján Plesník

Mathematica Slovaca (1982)

  • Volume: 32, Issue: 4, page 379-388
  • ISSN: 0139-9918

How to cite

top

Plesník, Ján. "Complexity of decomposing graphs into factors with given diameters or radii." Mathematica Slovaca 32.4 (1982): 379-388. <http://eudml.org/doc/34139>.

@article{Plesník1982,
author = {Plesník, Ján},
journal = {Mathematica Slovaca},
keywords = {diameter decomposition problem; radius decomposition problem; factor; NP- hardness},
language = {eng},
number = {4},
pages = {379-388},
publisher = {Mathematical Institute of the Slovak Academy of Sciences},
title = {Complexity of decomposing graphs into factors with given diameters or radii},
url = {http://eudml.org/doc/34139},
volume = {32},
year = {1982},
}

TY - JOUR
AU - Plesník, Ján
TI - Complexity of decomposing graphs into factors with given diameters or radii
JO - Mathematica Slovaca
PY - 1982
PB - Mathematical Institute of the Slovak Academy of Sciences
VL - 32
IS - 4
SP - 379
EP - 388
LA - eng
KW - diameter decomposition problem; radius decomposition problem; factor; NP- hardness
UR - http://eudml.org/doc/34139
ER -

References

top
  1. BARANOVlČOVA Z., On decomposition of complete 2-graphs into factors with given diameters, Acta Fac R. N. Univ. Comen. Math. 24, 1970, 175-180. (1970) MR0294153
  2. BEHZAD M., CHARTRAND G., LESNIAK FOSTER L., Graphs and Digraphs Prindle, Weber and Schmidt. Boston 1979. (1979) MR0525578
  3. BERGE C., Graphs and Hypergraphs, North Holland, London, 1973. (1973) Zbl0254.05101MR0357172
  4. BOLLOBAS B., Extremal Graph Theory, Academic Press. New York. 1978. (1978) Zbl0419.05031MR0506522
  5. BOSÁK J., Disjoint factors of diameter two in complete graphs, J. Combin. Theory B 16, 1974, 57-63. (1974) Zbl0256.05117MR0351901
  6. BOSÁK J., ERDOS P., ROSA A., Decomposition of complete graphs into factors with diameter two, Mat. časop 21, 1971, 14-28. (1971) MR0321798
  7. BOSÁK J., ROSA A., ZNÁM Š., On decompositions of complete graphs into factors with given diameters, In: Theory of graphs. Proc Colloq. Tihany 1966, Akademiai Kiado, Budapest, 1968, 37-56. (1966) MR0233720
  8. BŘEZINA J., Použitie samočinnych počitačov pri skumani istych rozkladov kompletneho grafu, Mat časop. 23, 1973, 17-33. (1973) MR0325459
  9. CHVATAL V., THOMASSEN C., Distances in orientations of graphs, J. Combin. Theory B 24, 1978, 61-75 (1978) MR0491326
  10. ERDÓS P., SAUER N., SCHAER J., SPENCER J., Factorizing the complete graph into factors with large star number, J. Combin. Theory B 18, 1975, 180-183. (1975) MR0364021
  11. GAREY M. R., JOHNSON D.S., Computers and Intractability, W. H. Freeman and Company. San Francisco, 1979. (1979) Zbl0411.68039MR0519066
  12. KAMEDA T., On maximally distant spanning trees of a graph, Computing 17, 1976, 115-119. (1976) Zbl0335.05102MR0424597
  13. KOTZIG A., ROSA A., Decomposition of complete graphs into isomorphic factors with a given diameter, Bull. London Math. Soc. 7, 1975, 51-57. (1975) Zbl0308.05128MR0369175
  14. LOVASZ L., Coverings and colorings of hypergraphs, Graph Theory and Computing (Hoffman F. et al., eds.), Utilitas Mathematica, Winnipeg, 1973, 3-12. (1973) Zbl0322.05114MR0363980
  15. NASH-WILLIAMS C. St. J. A., Edge-disjoint spanning trees of finite graphs, J. London Math. Soc. 36, 1961. 445-450. (1961) Zbl0102.38805MR0133253
  16. NIEPEL Ľ., O rozklade kompletneho hypergrafu na faktory s danymi priemermi, Acta Fac. R. N. Univ. Comen. Math 34, 1979, 21-28. (1979) MR0568331
  17. NIEPEL Ľ., On decomposition of complete graphs into factors with given diameters and radii, Math. Slovaca 30, 1980, 3-11. (1980) MR0568209
  18. PALUMBÍNY D., On a certain type of decompositions of complete graphs into factors with equal diameters, Mat. časop. 22, 1972, 235-242. (1972) Zbl0247.05160MR0351894
  19. PALUMBÍNY D., On decompositions of complete graphs into factors with equal diameters, Boll. Unione Mat. Ital. 7, 1973, 420-428. (1973) Zbl0264.05124MR0325465
  20. PALUMBÍNY D., ZNÁM Š., On decompositions of complete graphs into factors with given radii, Mat. časop. 23, 1973, 306-316. (1973) MR0340113
  21. SAUER N., On the factorization of the complete graph into factors of diameter 2, J. Combin. Theory 9, 1970, 423-426. (1970) MR0278987
  22. SAUER N., SCHAER J., On the factorization of the complete graph, J. Combin. Theory B 14, 1973, 1-6. (1973) Zbl0253.05144MR0313129
  23. TOMASTA P., Decompositions of complete k-uniform hypergraphs into factors with given diameters, Comment. Math. Univ. Carolinae 17, 1976, 377-392. (1976) Zbl0327.05129MR0472607
  24. TOMASTA P., Decompositions of graphs and hypergraphs into isomorphic factors with a given diameter, Czechoslovak Math. J. 27 (102), 1977, 598-608. (1977) Zbl0384.05048MR0472608
  25. TOMASTA P., On decompositions of complete k-uniform hypergraphs, Czechoslovak Math. J. 28 (103), 1978, 120-126. (1978) Zbl0375.05044MR0480170
  26. TOMOVÁ E., On the decompositions of the complete directed graph into factors with given diameters, Mat. časop. 20, 1970, 257-261. (1970) MR0309789
  27. TOMOVÁ E., Decomposition of complete bipartite graphs into factors with given diameters, Math. Slovaca 27, 1977, 113-128. (1977) Zbl0357.05066MR0476588
  28. TOMOVÁ E., Decomposition of complete bipartite graphs into factors with given radii, Math. Slovaca 27, 1977, 231-237. (1977) Zbl0357.05067MR0536139
  29. TUTTE W. T., On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 3, 1961, 221-230. (1961) Zbl0096.38001MR0140438
  30. ZNÁM Š., Decomposition of the complete directed graph into two factors with given diameters, Mat. časop. 20, 1970, 254-256. (1970) Zbl0206.52802MR0309790
  31. ZNÁM Š., Decomposition of complete graphs into factors of diameter two, Math. Slovaca 30, 1980, 373-378. (1980) Zbl0462.05052MR0595298
  32. ZNÁM Š., On a conjecture of Bollobás and Bosák, J. Graph. Theory 6, 1982, 139-146. (1982) Zbl0497.05049MR0655199

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.