On edge connectivity of direct products of graphs

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

Povzetek

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.

Ključne besede

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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2011
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	16006745
ISSN:	0020-0190
Št. ogledov:	52
Št. prenosov:	32
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	O povezanosti po povezavah direktnih produktov grafov
Sekundarni povzetek:	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)$▫.
Sekundarne ključne besede:	matematika;teorija grafov;kombinatorični problemi;povezanost;direktni produkt grafov;presečna množica;
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 899-902
Letnik:	ǂVol. ǂ111
Zvezek:	ǂiss. ǂ18
Čas izdaje:	2011
ID:	8718257