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

Povzetek

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

Ključne besede

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;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.12 - Objavljeni povzetek znanstvenega prispevka na konferenci
Organizacija: UM FS - Fakulteta za strojništvo
UDK: 519.17
COBISS: 13823577 Povezava se bo odprla v novem oknu
ISSN: 1571-0653
Št. ogledov: 1097
Št. prenosov: 90
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Algoritem za razpoznavanje kartezičnih grafovskih svežnjev
Sekundarni povzetek: 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.
Sekundarne ključne besede: Teorija grafov;
URN: URN:SI:UM:
Vrsta dela (COBISS): Članek v reviji
Strani: str. 217-221
Zvezek: ǂVol. ǂ3
Čas izdaje: May 1999
DOI: 10.1016/S1571-0653(05)80060-5
ID: 1472583
Priporočena dela:
, ni podatka o podnaslovu
, ni podatka o podnaslovu