PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 2 | 347-359
Tytuł artykułu

The Balanced Decomposition Number of TK4 and Series-Parallel Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V (G) = V1 ∪˙ · · · ∪˙ Vr such that, for every i, Vi induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G) was introduced by Fujita and Nakamigawa in 2008. They conjectured that f(G) ≤ ⌊n 2 ⌋ + 1 if G is a 2-connected graph on n vertices. In this paper, we shall prove two partial results, in the cases when G is a subdivided K4, and a 2-connected series-parallel graph.
Słowa kluczowe
Wydawca
Rocznik
Tom
33
Numer
2
Strony
347-359
Opis fizyczny
Daty
wydano
2013-05-01
online
2013-04-13
Twórcy
  • Department of Integrated Design Engineering Maebashi Institute of Technology 460-1 Kamisadori, Maebashi, 371-0816, Japan, shinyafujita@maebashi-it.ac.jp
autor
  • Departamento de Matemática Faculdade de Ciˆencias e Tecnologia Universidade Nova de Lisboa Quinta da Torre, 2829-516 Caparica, Portugal, h.liu@fct.unl.pt
Bibliografia
  • [1] B. Bollobás, Modern Graph Theory (Springer-Verlag, New York, 1998).
  • [2] R.J. Duffin, Topology of series-parallel networks, J. Math. Anal. Appl. 10 (1965) 303-318.
  • [3] E.S. Elmallah and C.J. Colbourn, Series-parallel subgraphs of planar graphs, Networks 22 (1992) 607-614. doi:10.1002/net.3230220608[Crossref]
  • [4] S. Fujita and H. Liu, The balanced decomposition number and vertex connectivity, SIAM. J. Discrete Math. 24 (2010) 1597-1616. doi:10.1137/090780894[WoS][Crossref]
  • [5] S. Fujita and H. Liu, Further results on the balanced decomposition number , in: Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 202 (2010) 119-128.
  • [6] S. Fujita and T. Nakamigawa, Balanced decomposition of a vertex-coloured graph, Discrete Appl. Math. 156 (2008) 3339-3344. doi:10.1016/j.dam.2008.01.006[Crossref]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1666
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.