Algorithm for recognizing Cartesian graph bundles

Blaž Zmazek (Author), Janez Žerovnik (Author)

Abstract

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$▫.

Keywords

matematika;teorija grafov;kartezični grafovski svežnji;enolična lokalna produktna lastnost;osnovna faktorizacija;razpoznavanje;polinomski algoritem;ne zaključna dela;mathematics;graph theory;Cartesian graph bundles;unique square property;fundamental factorization;polynomial algorithm;recognition;

Data

Language:	English
Year of publishing:	1999
Typology:	1.12 - Published Scientific Conference Contribution Abstract
Organization:	UM FS - Faculty of Mechanical Engineering
UDC:	519.17
COBISS:	13823577
ISSN:	1571-0653
Views:	1097
Downloads:	90
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Algoritem za razpoznavanje kartezičnih grafovskih svežnjev
Secondary 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.
Secondary keywords:	Teorija grafov;
URN:	URN:SI:UM:
Type (COBISS):	Article
Pages:	str. 217-221
Issue:	ǂVol. ǂ3
Chronology:	May 1999
DOI:	10.1016/S1571-0653(05)80060-5
ID:	1472583