Edge-connectivity of strong products of graphs
Abstract
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.
Keywords
matematika;teorija grafov;povezanost;krepki produkt;produkt grafov;presečna množica;mathematics;graph theory;connectivity;strong product;graph product;separating set;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2007 |
| Typology: | 1.01 - Original Scientific Article |
| Organization: | UM FS - Faculty of Mechanical Engineering |
| UDC: | 519.17 |
| COBISS: |
14368345
|
| ISSN: | 1234-3099 |
| Views: | 853 |
| Downloads: | 301 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | Slovenian |
|---|---|
| Secondary abstract: | 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. |
| Secondary keywords: | matematika;teorija grafov;povezanost;krepki produkt;produkt grafov;presečna množica; |
| URN: | URN:SI:UM: |
| Pages: | str. 333-343 |
| Volume: | ǂVol. ǂ27 |
| Issue: | ǂno. ǂ2 |
| Chronology: | 2007 |
| ID: | 9595934 |
Recommended works:
Edge-connectivity of strong products of graphs
2007,
no subtitle data available
On edge connectivity of direct products of graphs
2011,
no subtitle data available
Connectivity of Cartesian products of graphs
2008,
no subtitle data available
Chromatic numbers of strong product of odd cycles
2002,
no subtitle data available
NZ-flows in strong products of graphs
2010,
no subtitle data available