Discussiones Mathematicae Graph Theory 25(1-2) (2005)
217-218
doi: 10.7151/dmgt.1274
Adam Idzik
Akademia Świetokrzyska
15 Świetokrzyska street, 25-406 Kielce, Poland
and
Institute of Computer Science
Polish Academy of Sciences
21 Ordona street, 01-237 Warsaw, Poland
e-mail: adidzik@ipipan.waw.pl
All graphs considered here are finite simple graphs, i.e., graphs without loops, multiple edges or directed edges. For a graph G = (V,E), where V is a vertex set and E is an edge set, we write sometimes V(G) for V and E(G) for E to avoid ambiguity. We shall write G∖v instead of G_{V∖{v}} = (V∖{v},E∩2^{V∖{v}}), the subgraph induced by V∖{v}. A vertex v ∈ V(G) is called a cut-vertex of G if G is connected and G∖v is not. By a k-edge-colouring of a graph we mean any finite partition of the set of its edges into k subsets. A graph (V,E) with a given k-edge-colouring (E^{1},…,E^{k}) (E^{i}∩E^{j} = ∅ for i ± j; i,j ∈ {1,…,k} and ∪_{i ∈ {1,…,k}} E^{i} = E) is denoted by (V,E^{1},…,E^{k}). The graphs (V,E^{i}) are called monochromatic subgraphs of (V,E^{1},…,E^{k}), i ∈ {1,…,k}. As usual, by K_{m} we denote the complete graph with m vertices.
Let c(G^{i}) denote the number of cut-vertices of G^{i} in a monochromatic subgraph G^{i} = (V,E^{i}) of a k-edge-coloured complete graph K_{m} = (V,E^{1}, …,E^{k}) (i ∈ {1,…,k}).
Given a k-edge-coloured graph G = (V,E^{1}, …,E^{k}), we define F^{i} = E∖E^{i}, G^{i} = (V,E^{i}), G^{i} = (V,F^{i}), where E = ∪ _{i ∈ {1,… ,k}} E^{i} and i ∈ {1,…,k}. Here G^{i} is a monochromatic subgraph of G and G ^{i} its complement in G.
Theorem (Idzik, Tuza, Zhu). Let (E^{1},…
,E^{k}) be a k-edge-colouring of K_{m} (k ≥
2, m ≥ 4), such that all the graphs
G^{1},…
,G^{k} are connected.
Problem. Let (E^{1},…,
E^{k}) be a k-edge-colouring of K_{m}(k ≥ 2,
m ≥ 4). What is the cardinality of the set of the sum of
cut-vertices of G^{i}
in the case none of G^{i} is 2-connected and
(a) two of G^{i} are connected or (b) two of G^{i} are disconnected and
c(G^{i}) = 1 (i ∈
{1,…,k}) ?
(i)
If one of the subgraphs G^{1},…,G^{k} is 2-connected, say
G^{i}, then c(G^{i}) ≤ m
−2 and c(G
^{j}) = 0 for j ± i
(i,j ∈ {1,...,k}).
(ii)
If none of the graphs G^{1},…,
G^{k} is 2-connected, and one
of them is connected, say G^{i}, then c(G^{i}) ≤
2 (i ∈ {1,…,k}).
(iii)
If none of the graphs G^{1},…,G^{k}
is 2-connected, and one
of them is disconnected, say G^{i}, then c(G^{i})
≤ 1 (i ∈ {1,…,k}).
Observe that in both cases (a) and (b) all the graphs G ^{1},…,G^{k} are connected.
This problem is related to some theorems presented in [1] and [2].
[1] | J. Bosák, A. Rosa and S. Znám, On decompositions of complete graphs into factors with given diameters, in: P. Erdős and G. Katona, eds., Theory of Graphs, Proceedings of the Colloquium Held at Tihany, Hungary (Academic Press, New York, 1968) 37-56. |
[2] | A. Idzik and Z. Tuza, Heredity properties of connectedness in edge-coloured complete graphs, Discrete Math. 235 (2001) 301-306, doi: 10.1016/S0012-365X(00)00282-X. |
Received 21 November 2003