Spanning tree congestion of rook's graphs

Kyohei Kozawa; Yota Otachi

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 4, page 753-761
  • ISSN: 2083-5892

Abstract

top
Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.

How to cite

top

Kyohei Kozawa, and Yota Otachi. "Spanning tree congestion of rook's graphs." Discussiones Mathematicae Graph Theory 31.4 (2011): 753-761. <http://eudml.org/doc/270973>.

@article{KyoheiKozawa2011,
abstract = {Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.},
author = {Kyohei Kozawa, Yota Otachi},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {spanning tree congestion; Rook's graph; rook's graph},
language = {eng},
number = {4},
pages = {753-761},
title = {Spanning tree congestion of rook's graphs},
url = {http://eudml.org/doc/270973},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Kyohei Kozawa
AU - Yota Otachi
TI - Spanning tree congestion of rook's graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 4
SP - 753
EP - 761
AB - Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.
LA - eng
KW - spanning tree congestion; Rook's graph; rook's graph
UR - http://eudml.org/doc/270973
ER -

References

top
  1. [1] J. Balogh and D. Mubayi and A. Pluhár, On the edge-bandwidth of graph products, Theoret. Comput. Sci. 359 (2006) 43-57, doi: 10.1016/j.tcs.2006.01.046. Zbl1098.05070
  2. [2] A. Bekmetjev and G. Hurlbert, The pebbling threshold of the square of cliques, Discrete Math. 308 (2008) 4306-4314, doi: 10.1016/j.disc.2007.08.012. Zbl1152.05050
  3. [3] S.L. Bezrukov, Edge isoperimetric problems on graphs, in: L. Lovasz, A. Gyarfas, G.O.H. Katona, A. Recski and L. Szekely, eds, Graph Theory and Combinatorial Biology, 7 Bolyai Soc. Math. Stud. 157-197 Janos Bolyai Math. Soc. (Budapest, 1999). Zbl0927.05080
  4. [4] H.L. Bodlaender, K. Kozawa, T. Matsushima and Y. Otachi, Spanning Tree Congestion of k-outerplanar Graphs, in: WAAC 2010 (2010) 34-39. Zbl1223.05017
  5. [5] A. Castejón and M.I. Ostrovskii, Minimum congestion spanning trees of grids and discrete toruses, Discuss. Math. Graph Theory 29 (2009) 511-519, doi: 10.7151/dmgt.1461. Zbl1193.05058
  6. [6] M. Chudnovsky and N. Robertson and P. Seymour and R. Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006) 51-229, doi: 10.4007/annals.2006.164.51. Zbl1112.05042
  7. [7] A.J. Hoffman, On the Line Graph of the Complete Bipartite Graph, Ann. Math. Statist. 35 (1964) 883-885, doi: 10.1214/aoms/1177703593. Zbl0127.39302
  8. [8] S.W. Hruska, On tree congestion of graphs, Discrete Math. 308 (2008) 1801-1809, doi: 10.1016/j.disc.2007.04.030. Zbl1151.05014
  9. [9] K. Kozawa and Y. Otachi and K. Yamazaki, On spanning tree congestion of graphs, Discrete Math. 309 (2009) 4215-4224, doi: 10.1016/j.disc.2008.12.021. Zbl1232.05116
  10. [10] C. Löwenstein and D. Rautenbach and F. Regen, On spanning tree congestion, Discrete Math. 309 (2009) 4653-4655, doi: 10.1016/j.disc.2009.01.012. Zbl1213.05093
  11. [11] R. Laskar and C. Wallis, Chessboard graphs, related designs, and domination parameters, J. Statist. Plann. Inference 76 (1999) 285-294, doi: 10.1016/S0378-3758(98)00132-3. Zbl0939.05065
  12. [12] H.-F. Law, Spanning tree congestion of the hypercube, Discrete Math. 309 (2009) 6644-6648, doi: 10.1016/j.disc.2009.07.007. Zbl1179.05032
  13. [13] J.H. Lindsey II, Assignment of numbers to vertices, Amer. Math. Monthly 71 (1964) 508-516, doi: 10.2307/2312587. 
  14. [14] J.W. Moon, On the Line-Graph of the Complete Bigraph, Ann. Math. Statist. 34 (1963) 664-667, doi: 10.1214/aoms/1177704179. Zbl0138.19204
  15. [15] M.I. Ostrovskii, Minimum congestion spanning trees in planar graphs, Discrete Math. 310 (2010) 1204-1209, doi: 10.1016/j.disc.2009.11.016. Zbl1230.05112
  16. [16] M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219-226, doi: 10.1016/j.disc.2004.02.009. Zbl1051.05032
  17. [17] Y. Otachi, H.L. Bodlaender and E.J. van Leeuwen, Complexity Results for the Spanning Tree Congestion Problem, in: WG 2010, 6410 Lecture Notes in Comput. Sci. (Springer-Verlag, 2010) 3-14. Zbl1308.68067
  18. [18] S. Simonson, A variation on the min cut linear arrangement problem, Math. Syst. Theory 20 (1987) 235-252, doi: 10.1007/BF01692067. Zbl0643.68094

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.