Recognizing weighted directed cartesian graph bundles

Blaz Zmazek; Janez Zerovnik

Discussiones Mathematicae Graph Theory (2000)

  • Volume: 20, Issue: 1, page 39-56
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Blaz Zmazek, and Janez Zerovnik. "Recognizing weighted directed cartesian graph bundles." Discussiones Mathematicae Graph Theory 20.1 (2000): 39-56. <http://eudml.org/doc/270293>.

@article{BlazZmazek2000,
abstract = {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.},
author = {Blaz Zmazek, Janez Zerovnik},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph bundles; Cartesian graph product; weighted digraphs; half-convexity; recognizing Cartesian graph bundles},
language = {eng},
number = {1},
pages = {39-56},
title = {Recognizing weighted directed cartesian graph bundles},
url = {http://eudml.org/doc/270293},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Blaz Zmazek
AU - Janez Zerovnik
TI - Recognizing weighted directed cartesian graph bundles
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 1
SP - 39
EP - 56
AB - 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.
LA - eng
KW - graph bundles; Cartesian graph product; weighted digraphs; half-convexity; recognizing Cartesian graph bundles
UR - http://eudml.org/doc/270293
ER -

References

top
  1. [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. Zbl0763.05035
  2. [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. Zbl0579.68028
  3. [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. Zbl0637.05018
  4. [4] W. Imrich, Factoring Cardinal Product Graphs in Polynomial Time, Discrete Math. 192 (1998). 
  5. [5] W. Imrich and J. Zerovnik, Factoring Cartesian-product Graphs, J. Graph Theory 18 (1994) 557-567. Zbl0811.05054
  6. [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. Zbl0876.05094
  7. [7] S. Klavžar and B. Mohar, Coloring graph bundles, J. Graph Theory 19 (1995) 145-155, doi: 10.1002/jgt.3190190203. Zbl0815.05029
  8. [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. Zbl0818.05035
  9. [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. Zbl0739.05042
  10. [10] B. Mohar, T. Pisanski and M. Skoveira, The maximum genus of graph bundles, European J. Combin. 9 (1988) 301-314. 
  11. [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. Zbl0505.05034
  12. [12] T. Pisanski and J. Vrabec, Graph bundles, unpublished manuscript, 1982. 
  13. [13] T. Pisanski, B. Zmazek and J. Zerovnik, An algorithm for k-convex closure and an application, submitted. Zbl0983.05075
  14. [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. Zbl0434.05037
  15. [15] G. Sabidussi, Graph Multiplication, Mathematische Zeitschrift 72 (1960) 446-457, doi: 10.1007/BF01162967. Zbl0093.37603
  16. [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. Zbl0808.05073
  17. [17] B. Zmazek, J. Zerovnik, On Recognizing Cartesian Graph Bundles, accepted, Discrete Math. Zbl0988.05065
  18. [18] B. Zmazek, J. Zerovnik, Unique Square Property and Fundamental Factorization, accepted, Discrete Math. 
  19. [19] B. Zmazek, J. Zerovnik, Algorithm for Recognizing Cartesian Graph Bundles, submitted. Zbl1004.05055
  20. [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. Zbl0587.05056
  21. [21] J. Zerovnik, On Recognition of Strong Graph Bundles, accepted, Math. Slovaca. Zbl0984.05068

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.