Edge-connectivity of strong products of graphs

Boštjan Brešar (Avtor), Simon Špacapan (Avtor)

Povzetek

Krepki produkt ▫$G_1\boxtimes G_2$▫ grafov ▫$G_1$▫ in ▫$G_2$▫ je graf, katerega množica vozlišč je ▫$V(G_1)\times V(G_2)$▫, dve različni vozlišč ▫$(x_1,x_2)$▫ in ▫$(y_1,y_2)$▫ pa sta povezani natanko tedaj, ko za vsak ▫$i\in \{1,2\}$▫ velja ▫$x_i=y_i$▫ ali ▫$x_iy_i \in E(G_i)$▫. V članku dokažemo, da je za poljubna povezana grafa ▫$G_1$ in $G_2$▫ povezanost po povezavah njunega krepkega produkta ▫$\lambda(G_1 \boxtimes G_2)$▫ enaka $\min\{\delta(G_1\boxtimes G_2), \lambda(G_1)(|V(G_2)|+2|E(G_2)|), \lambda(G_2)(|V(G_1)|+2|E(G_1)|)\}$. Poleg tega v celoti opišemo strukturo možnih najmanših presečnih množic v krepkem produktu grafov.

Ključne besede

matematika;teorija grafov;povezanost;krepki produkt;produkt grafov;presečna množica;mathematics;graph theory;connectivity;strong product;graph product;separating set;

Podatki

Jezik:	Angleški jezik
Leto izida:	2007
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	14368345
ISSN:	1234-3099
Št. ogledov:	853
Št. prenosov:	301
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni povzetek:	The strong product ▫$G_1 \boxtimes G_2$▫ of graphs ▫$G_1$▫ and ▫$G_2$▫ is the graph with ▫$V(G_1) \times V(G_2)$▫ as the vertex set, and two distinct vertices ▫$(x_1,x_2)$▫ and ▫$(y_1,y_2)$▫ are adjacent whenever for each ▫$i\in \{1,2\}$▫ either ▫$x_i=y_i$▫ or ▫$x_iy_i \in E(G_i)$▫. In this note we show that for two connected graphs ▫$G_1$▫ and ▫$G_2$▫ the edge-connectivity ▫$\lambda(G_1 \boxtimes G_2)$▫ equals ▫$\min\{\delta(G_1\boxtimes G_2), \lambda(G_1)(\|V(G_2)\|+2\|E(G_2)\|), \lambda(G_2)(\|V(G_1)\|+2\|E(G_1)\|)\}$▫. In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.
Sekundarne ključne besede:	matematika;teorija grafov;povezanost;krepki produkt;produkt grafov;presečna množica;
URN:	URN:SI:UM:
Strani:	str. 333-343
Letnik:	ǂVol. ǂ27
Zvezek:	ǂno. ǂ2
Čas izdaje:	2007
ID:	9595934