| Naslov: | On edge connectivity of direct products of graphs |
|---|
| Avtorji: | ID Cao, Xiang-Lan (Avtor)
ID Brglez, Špela (Avtor)
ID Špacapan, Simon (Avtor)
ID Vumar, Elkin (Avtor) |
|---|
| Datoteke: |  http://dx.doi.org/10.1016/j.ipl.2011.06.007
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Neznano |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FS - Fakulteta za strojništvo
|
|---|
| Opis: | 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)$▫. |
|---|
| Ključne besede: | mathematics, graph theory, combinatorial problems, connectivity, direct product, graph product, separating set |
|---|
| Leto izida: | 2011 |
|---|
| PID: | 20.500.12556/DKUM-26959  |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 16006745 |
|---|
| ISSN pri članku: | 0020-0190 |
|---|
| NUK URN: | URN:SI:UM:DK:HIJLUXNW |
|---|
| Datum objave v DKUM: | 01.06.2012 |
|---|
| Število ogledov: | 2512 |
|---|
| Število prenosov: | 227 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
