| Title: | On edge connectivity of direct products of graphs |
|---|
| Authors: | ID Cao, Xiang-Lan (Author)
ID Brglez, Špela (Author)
ID Špacapan, Simon (Author)
ID Vumar, Elkin (Author) |
|---|
| Files: |  http://dx.doi.org/10.1016/j.ipl.2011.06.007
|
|---|
| Language: | English |
|---|
| Work type: | Unknown |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FS - Faculty of Mechanical Engineering
|
|---|
| 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)$▫. |
|---|
| Keywords: | mathematics, graph theory, combinatorial problems, connectivity, direct product, graph product, separating set |
|---|
| Year of publishing: | 2011 |
|---|
| PID: | 20.500.12556/DKUM-26959  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0020-0190 |
|---|
| COBISS.SI-ID: | 16006745 |
|---|
| NUK URN: | URN:SI:UM:DK:HIJLUXNW |
|---|
| Publication date in DKUM: | 01.06.2012 |
|---|
| Views: | 2508 |
|---|
| Downloads: | 227 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
