PDF

Discussiones Mathematicae Graph Theory 25(1-2) (2005) 217-218
DOI: https://doi.org/10.7151/dmgt.1274

ESTIMATION OF CUT-VERTICES IN EDGE-COLOURED COMPLETE GRAPHS

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¹,…,E^k) (Eⁱ∩E^j = ∅ for i ± j; i,j ∈ {1,…,k} and ∪_{i ∈ {1,…,k}} Eⁱ = E) is denoted by (V,E¹,…,E^k). The graphs (V,Eⁱ) are called monochromatic subgraphs of (V,E¹,…,E^k), i ∈ {1,…,k}. As usual, by K_m we denote the complete graph with m vertices.

     Let c(Gⁱ) denote the number of cut-vertices of Gⁱ in a monochromatic subgraph Gⁱ = (V,Eⁱ) of a k-edge-coloured complete graph K_m = (V,E¹, …,E^k)  (i ∈ {1,…,k}).

     Given a k-edge-coloured graph G = (V,E¹, …,E^k), we define Fⁱ = E∖Eⁱ, Gⁱ = (V,Eⁱ), Gⁱ = (V,Fⁱ), where E = ∪ _{i ∈ {1,… ,k}} Eⁱ and i ∈ {1,…,k}. Here Gⁱ is a monochromatic subgraph of G and G ⁱ its complement in G.

Theorem (Idzik, Tuza, Zhu). Let (E¹,… ,E^k) be a k-edge-colouring of K_m (k ≥ 2, m ≥ 4), such that all the graphs G¹,… ,G^k are connected.

(i)	If one of the subgraphs G1,…,Gk is 2-connected, say Gi, then c(Gi) ≤ m −2 and c(G j) = 0 for j ± i (i,j ∈ {1,...,k}).
(ii)	If none of the graphs G1,…, Gk is 2-connected, and one of them is connected, say Gi, then c(Gi) ≤ 2 (i ∈ {1,…,k}).
(iii)	If none of the graphs G1,…,Gk is 2-connected, and one of them is disconnected, say Gi, then c(Gi) ≤ 1 (i ∈ {1,…,k}).

Problem. Let (E¹,…, 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ⁱ in the case none of Gⁱ is 2-connected and (a) two of Gⁱ are connected or (b) two of Gⁱ are disconnected and c(Gⁱ) = 1 (i ∈ {1,…,k}) ?

Observe that in both cases (a) and (b) all the graphs G ¹,…,G^k are connected.

     This problem is related to some theorems presented in [1] and [2].

References

[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