Algorithm for recognizing Cartesian graph bundles

Zmazek, Blaž; Žerovnik, Janez

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Algorithm for recognizing Cartesian graph bundles
Authors:	ID Zmazek, Blaž (Author) ID Žerovnik, Janez (Author)
Files:	http://dx.doi.org/10.1016/S1571-0653(05)80060-5
Language:	English
Work type:	Article
Typology:	1.12 - Published Scientific Conference Contribution Abstract
Organization:	PEF - Faculty of Education
Abstract:	Graph bundles generalize the notion of covering graphs and graphs products. Authors W. Imrich, T. Pisanski and J. Žerovnik constructed an algorithm that finds a presentation as a nontrivial Cartesian graph bundle for all graphs that are Cartesian graph bundles over triangle-free simple base (Discrete Math. 167, 168 (1998) 393-403). The uniquesquare property is defined in Discrete Math., 244 (2002) 551-561, and it is shown that any equivalence relation possesing the unique square property determines the fundamental factorization of a graph as a nontrivial Cartesian graph bundle over arbitrary base graph. In this paper we define the relation $Delta$ having the unique square property on Cartesian graph bundles over $K_4 setminus e$ -free simple base. We also give a polynomial algorithm for recognizing Cartesian graph bundles over $K_4 setminus e$ -simple base.
Keywords:	matematika, teorija grafov, kartezični grafovski svežnji, enolična lokalna produktna lastnost, osnovna faktorizacija, razpoznavanje, polinomski algoritem, mathematics, graph theory, Cartesian graph bundles, unique square property, fundamental factorization, polynomial algorithm, recognition
Year of publishing:	1999
Number of pages:	str. 217-221
Numbering:	Vol. 3
PID:	20.500.12556/DKUM-51506
UDC:	519.17
ISSN on article:	1571-0653
COBISS.SI-ID:	13823577
NUK URN:	URN:SI:UM:DK:YKISPYTP
Publication date in DKUM:	10.07.2015
Views:	1258
Downloads:	95
Metadata:
Categories:	Misc.
:	ZMAZEK, Blaž and ŽEROVNIK, Janez, 1999, Algorithm for recognizing Cartesian graph bundles. In : Electronic notes in discrete mathematics [online]. Published Scientific Conference Contribution Abstract. 1999. p. 217–221. [Accessed 2 April 2025]. Retrieved from: http://dx.doi.org/10.1016/S1571-0653(05)80060-5 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:	Electronic notes in discrete mathematics
Publisher:	Elsevier
ISSN:	1571-0653
COBISS.SI-ID:	13803097

Secondary language

Language:	Slovenian
Title:	Algoritem za razpoznavanje kartezičnih grafovskih svežnjev
Abstract:	Graph bundles generalize the notion of covering graphs and graphs products. Authors W. Imrich, T. Pisanski and J. Žerovnik constructed an algorithm that finds a presentation as a nontrivial Cartesian graph bundle for all graphs that are Cartesian graph bundles over triangle-free simple base (Discrete Math. 167, 168 (1998) 393-403). The uniquesquare property is defined in Discrete Math., 244 (2002) 551-561, and it is shown that any equivalence relation possesing the unique square property determines the fundamental factorization of a graph as a nontrivial Cartesian graph bundle over arbitrary base graph. In this paper we define the relation $Delta$ having the unique square property on Cartesian graph bundles over $K_4 setminus e$ -free simple base. We also give a polynomial algorithm for recognizing Cartesian graph bundles over $K_4 setminus e$ -simple base. Grafovski svežnji predstavljajo posplošitev krovnih in produktnih grafov. V članku vpeljemo enolično lokalno produktno relacijo $Delta$ na kartezičnih svežnjih nad baznimi grafi, ki ne vsebujejo grafa $K_4 setminus e$ in podamo algoritem za razpoznavanje kartezičnih svežnjev nad enostavnimi baznimi grafi brez $K_4 setminus e$ .

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back