Edge-connectivity of strong products of graphs

Brešar, Boštjan; Špacapan, Simon

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Edge-connectivity of strong products of graphs
Authors:	ID Brešar, Boštjan (Author) ID Špacapan, Simon (Author)
Files:	Discussiones_Mathematicae_Graph_Theory_2007_Bresar,_Spacapan_Edge-connectivity_of_strong_products_of_graphs.pdf (173,26 KB) MD5: D34D8D01A73C898EFF74C0C05FF0E75C http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1365
Language:	English
Work type:	Unknown
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
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.
Keywords:	mathematics, graph theory, connectivity, strong product, graph product, separating set
Publication status:	Published
Publication version:	Version of Record
Year of publishing:	2007
Number of pages:	str. 333-343
Numbering:	Letn. 27, št. 2
PID:	20.500.12556/DKUM-65338
ISSN:	1234-3099
UDC:	519.17
ISSN on article:	1234-3099
COBISS.SI-ID:	14368345
NUK URN:	URN:SI:UM:DK:IXOITPK7
Publication date in DKUM:	31.03.2017
Views:	1447
Downloads:	372
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan and ŠPACAPAN, Simon, 2007, Edge-connectivity of strong products of graphs. Discussiones mathematicae : Graph theory [online]. 2007. Vol. 27, no. 2, p. 333–343. [Accessed 2 April 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=65338 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

No similar works found

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Discussiones mathematicae : Graph theory
Shortened title:	Discuss. Math., Graph Theory
Publisher:	Technical University Press
ISSN:	1234-3099
COBISS.SI-ID:	7487065

Document is financed by a project

Funder:	Other - Other funder or multiple funders
Project number:	P1-0297
Name:	Teorija grafov

Licences

License:	CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Link:	http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:	The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:	31.03.2017

Secondary language

Language:	Slovenian
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

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back