Recognizing weighted directed cartesian graph bundles

• Autorzy: Blaz Zmazek , Janez Zerovnik
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph bundles; Cartesian graph product; weighted digraphs; half-convexity

Kategorie tematyczne

• 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2000
• Tom: 20
• Numer: 1
• Strony: 39-56

Daty

wydano

2000

otrzymano

1999-01-08

poprawiono

2000-03-16

Twórcy

autor

Blaz Zmazek

• Department of Mathematics, PEF, University of Maribor, Koroska 160, si-2000 Maribor, Slovenia

autor

Janez Zerovnik

• FME, University of Maribor, Smetanova 17, si-2000 Maribor, Slovenia

Bibliografia

• [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.
• [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.
• [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.
• [4] W. Imrich, Factoring Cardinal Product Graphs in Polynomial Time, Discrete Math. 192 (1998).
• [5] W. Imrich and J. Zerovnik, Factoring Cartesian-product Graphs, J. Graph Theory 18 (1994) 557-567.
• [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.
• [7] S. Klavžar and B. Mohar, Coloring graph bundles, J. Graph Theory 19 (1995) 145-155, doi: 10.1002/jgt.3190190203.
• [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.
• [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.
• [10] B. Mohar, T. Pisanski and M. Skoveira, The maximum genus of graph bundles, European J. Combin. 9 (1988) 301-314.
• [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.
• [12] T. Pisanski and J. Vrabec, Graph bundles, unpublished manuscript, 1982.
• [13] T. Pisanski, B. Zmazek and J. Zerovnik, An algorithm for k-convex closure and an application, submitted.
• [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.
• [15] G. Sabidussi, Graph Multiplication, Mathematische Zeitschrift 72 (1960) 446-457, doi: 10.1007/BF01162967.
• [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.
• [17] B. Zmazek, J. Zerovnik, On Recognizing Cartesian Graph Bundles, accepted, Discrete Math.
• [18] B. Zmazek, J. Zerovnik, Unique Square Property and Fundamental Factorization, accepted, Discrete Math.
• [19] B. Zmazek, J. Zerovnik, Algorithm for Recognizing Cartesian Graph Bundles, submitted.
• [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.
• [21] J. Zerovnik, On Recognition of Strong Graph Bundles, accepted, Math. Slovaca.

Identyfikatory

DOI

10.7151/dmgt.1105