On edge connectivity of direct products of graphs

Cao, Xiang-Lan; Brglez, Špela; Špacapan, Simon; Vumar, Elkin

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

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:	2320
Downloads:	224
Metadata:
Categories:	Misc.
:	CAO, Xiang-Lan, BRGLEZ, Špela, ŠPACAPAN, Simon and VUMAR, Elkin, 2011, On edge connectivity of direct products of graphs. Information processing letters [online]. 2011. [Accessed 23 April 2025]. Retrieved from: http://dx.doi.org/10.1016/j.ipl.2011.06.007 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:

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:	Information processing letters
Shortened title:	Inf. process. lett.
Publisher:	North-Holland
ISSN:	0020-0190
COBISS.SI-ID:	25612800

Secondary language

Language:	Slovenian
Title:	O povezanosti po povezavah direktnih produktov grafov
Abstract:	V članku študiramo povezanost po povezavah direktnih produktov grafov. Dokazana je formula za povezanost po povezavah direktnega produkta grafa $G$ s polnim grafom $K_n$ . Formula se glasi: $lambda(G times K_n) = min{n(n-1)lambda(G), (n-1)delta(G)}$ , kjer $lambda(G)$ označuje povezanost po povezavah grafa $G$ in $delta(G)$ njegovo najmanjšo stopnjo.
Keywords:	matematika, teorija grafov, kombinatorični problemi, povezanost, direktni 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