Recognizing weighted directed cartesian graph bundles
Blaz Zmazek ; Janez Zerovnik
Discussiones Mathematicae Graph Theory, Tome 20 (2000), p. 39-56 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this paper we show that methods for recognizing Cartesian graph bundles can be generalized to weighted digraphs. The main result is an algorithm which lists the sets of degenerate arcs for all representations of digraph as a weighted directed Cartesian graph bundle over simple base digraphs not containing transitive tournament on three vertices. Two main notions are used. The first one is the new relation →δ*defined among the arcs of a digraph as a weighted directed analogue of the well-known relation δ*. The second one is the concept of half-convex subgraphs. A subgraph H is half-convex in G if any vertex x ∈ G∖H has at most one predecessor and at most one successor.

Publié le : 2000-01-01
EUDML-ID : urn:eudml:doc:270293 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1105,
     author = {Blaz Zmazek and Janez Zerovnik},
     title = {Recognizing weighted directed cartesian graph bundles},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {20},
     year = {2000},
     pages = {39-56},
     zbl = {0966.05049},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1105}
}

Blaz Zmazek; Janez Zerovnik. Recognizing weighted directed cartesian graph bundles. Discussiones Mathematicae Graph Theory, Tome 20 (2000) pp. 39-56. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1105/

[000] [1] J. Abello, M.R. Fellows and J.C. Stillwell, On the Complexity and Combinatorics of Covering Finite Complexes, Australasian J. Combin. 4 (1991) 103-112. | Zbl 0763.05035

[001] [2] J. Feigenbaum, J. Hershberger and A.A. Schäffer, A Polynomial Time Algorithm for Finding the Prime Factors of Cartesian-Product Graphs, Discrete Appl. Math. 12 (1985) 123-138, doi: 10.1016/0166-218X(85)90066-6. | Zbl 0579.68028

[002] [3] J. Feigenbaum, Directed Cartesian-product Graphs have Unique Factorizations that can be Computed in Polynomial Time, Discrete Appl. Math. 15 (1986) 105-110, doi: 10.1016/0166-218X(86)90023-5. | Zbl 0637.05018

[003] [4] W. Imrich, Factoring Cardinal Product Graphs in Polynomial Time, Discrete Math. 192 (1998).

[004] [5] W. Imrich and J. Zerovnik, Factoring Cartesian-product Graphs, J. Graph Theory 18 (1994) 557-567. | Zbl 0811.05054

[005] [6] W. Imrich, T. Pisanski and J. Zerovnik, Recognizing Cartesian Graph Bundles, Discrete Math. 167/168 (1997) 393-403, doi: 10.1016/S0012-365X(96)00242-7. | Zbl 0876.05094

[006] [7] S. Klavžar and B. Mohar, Coloring graph bundles, J. Graph Theory 19 (1995) 145-155, doi: 10.1002/jgt.3190190203. | Zbl 0815.05029

[007] [8] S. Klavžar and B. Mohar, The chromatic numbers of graph bundles over cycles, Discrete Math. 138 (1995) 301-314, doi: 10.1016/0012-365X(94)00212-2. | Zbl 0818.05035

[008] [9] J.H. Kwak and J. Lee, Isomorphism classes of graph bundles, Canadian J. Math. 42 (1990) 747-761, doi: 10.4153/CJM-1990-039-3. | Zbl 0739.05042

[009] [10] B. Mohar, T. Pisanski and M. Skoveira, The maximum genus of graph bundles, European J. Combin. 9 (1988) 301-314.

[010] [11] T. Pisanski, J. Shawe-Taylor and J. Vrabec, Edge-colorability of graph bundles, J. Combin. Theory (B) 35 (1983) 12-19, doi: 10.1016/0095-8956(83)90076-X. | Zbl 0505.05034

[011] [12] T. Pisanski and J. Vrabec, Graph bundles, unpublished manuscript, 1982.

[012] [13] T. Pisanski, B. Zmazek and J. Zerovnik, An algorithm for k-convex closure and an application, submitted. | Zbl 0983.05075

[013] [14] K.B. Reid and L.W. Beineke, Tournaments, in: L.W. Beineke and R.J. Wilson, eds., Selected Topics in Graph Theory I (Academic Press, London 1978), 169-204. | Zbl 0434.05037

[014] [15] G. Sabidussi, Graph Multiplication, Mathematische Zeitschrift 72 (1960) 446-457, doi: 10.1007/BF01162967. | Zbl 0093.37603

[015] [16] M.Y. Sohn and J. Lee, Characteristic polynomials of some weighted graph bundles and its application to links, Internat. J. Math. & Math. Sci. 17 (1994) 504-510, doi: 10.1155/S0161171294000748. | Zbl 0808.05073

[016] [17] B. Zmazek, J. Zerovnik, On Recognizing Cartesian Graph Bundles, accepted, Discrete Math. | Zbl 0988.05065

[017] [18] B. Zmazek, J. Zerovnik, Unique Square Property and Fundamental Factorization, accepted, Discrete Math.

[018] [19] B. Zmazek, J. Zerovnik, Algorithm for Recognizing Cartesian Graph Bundles, submitted. | Zbl 1004.05055

[019] [20] J.W. Walker, Strict Refinement for Graphs and Digraphs, J. Combin. Theory (B) 43 (1987) 140-150, doi: 10.1016/0095-8956(87)90018-9. | Zbl 0587.05056

[020] [21] J. Zerovnik, On Recognition of Strong Graph Bundles, accepted, Math. Slovaca. | Zbl 0984.05068