On edge connectivity of direct products of graphs

Xiang-Lan Cao (Author), Špela Brglez (Author), Simon Špacapan (Author), Elkin Vumar (Author)

Abstract

V članku študiramo povezanost po povezavah direktnih produktov grafov. Dokazana je formula za povezanost po povezavah direktnega produkta grafa ▫$G$▫ s polnim grafom ▫$K_n$▫. Formula se glasi: ▫$\lambda(G \times K_n) = \min\{n(n-1)\lambda(G), (n-1)\delta(G)\}$▫, kjer ▫$\lambda(G)$▫ označuje povezanost po povezavah grafa ▫$G$▫ in ▫$\delta(G)$▫ njegovo najmanjšo stopnjo.

Keywords

matematika;teorija grafov;kombinatorični problemi;povezanost;direktni produkt grafov;presečna množica;mathematics;graph theory;combinatorial problems;connectivity;direct product;graph product;separating set;

Data

Language:	English
Year of publishing:	2011
Typology:	1.01 - Original Scientific Article
Organization:	UM FS - Faculty of Mechanical Engineering
UDC:	519.17
COBISS:	16006745
ISSN:	0020-0190
Views:	52
Downloads:	32
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	O povezanosti po povezavah direktnih produktov grafov
Secondary abstract:	Let ▫$\lambda(G)$▫ be the edge connectivity of ▫$G$▫. The direct product of graphs ▫$G$▫ and ▫$H$▫ is the graph with vertex set ▫$V(G \times H) = V(G) \times V(H)$▫, where two vertices ▫$(u_1,v_1)$▫ and ▫$(u_2,v_2)$▫ are adjacent in ▫$G \times H$▫ if ▫$u_1u_2 \in E(G)$▫ and ▫$v_1v_2 \in E(H)$▫. We prove that ▫$\lambda(G \times K_n) = \min\{n(n-1)\lambda(G), (n-1)\delta(G)\}$▫ for every nontrivial graph ▫$G$▫ and ▫$n \geqslant 3$▫. We also prove that for almost every pair of graphs ▫$G$▫ and ▫$H$▫ with ▫$n$▫ vertices and edge probability ▫$p$▫, ▫$G \times H$▫ is ▫$k$▫-connected, where ▫$k=O((n/\log n)^2)$▫.
Secondary keywords:	matematika;teorija grafov;kombinatorični problemi;povezanost;direktni produkt grafov;presečna množica;
Type (COBISS):	Not categorized
Pages:	str. 899-902
Volume:	ǂVol. ǂ111
Issue:	ǂiss. ǂ18
Chronology:	2011
ID:	8718257