11. |
12. |
13. Nove karakterizacije v strukturni teoriji grafov : 1-popolno usmerljivi grafi, produktni grafi in cena povezanostiTatiana Romina Hartinger, 2017, doctoral dissertation Keywords: 1-perfectly orientable graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph, block-cactus graph, cobipartite graph, K4-minor-free graph, outerplanar graph, graph product, Cartesian product, lexicographic product, direct product, strong product, price of connectivity, cycle transversal, path transversal
Published in RUP: 09.11.2017; Views: 5580; Downloads: 44
 Link to full text |
14. On cyclic edge-connectivity of fullerenesKlavdija Kutnar, Dragan Marušič, 2008, original scientific article Abstract: A graph is said to be cyclically ▫$k$▫-edge-connected, if at least ▫$k$▫ edges must be removed to disconnect it into two components, each containing a cycle. Such a set of ▫$k$▫ edges is called a cyclic-k-edge cutset and it is called a trivial cyclic-k-edge cutset if at least one of the resulting two components induces a single ▫$k$▫-cycle. It is known that fullerenes, that is, 3-connected cubic planar graphs all of whose faces are pentagons and hexagons, are cyclically 5-edge-connected. In this article it is shown that a fullerene ▫$F$▫ containing a nontrivial cyclic-5-edge cutset admits two antipodal pentacaps, that is, two antipodal pentagonal faces whose neighboring faces are also pentagonal. Moreover, it is shown that ▫$F$▫ has a Hamilton cycle, and as a consequence at least ▫$15 \cdot 2^{n/20-1/2}$▫ perfect matchings, where ▫$n$▫ is the order of ▫$F$▫.
Keywords: graph, fullerene graph, cyclic edge-connectivity, hamilton cycle, perfect matching
Published in RUP: 03.04.2017; Views: 3461; Downloads: 143
Link to full text |
15. Določeni razredi (hiper)grafov in njihove algebraične lastnosti : doktorska disertacijaPaweł Petecki, 2016, doctoral dissertation Keywords: hypergraph, hamiltonian cycle, decomposition, double generalized Petersen graph, automorphism group, vertex-transitive, sign graph, L-eigenvalue, lollipop graph
Published in RUP: 09.08.2016; Views: 4820; Downloads: 35
Link to full text |
16. |
17. |
18. Arc-transitive cycle decompositions of tetravalent graphsŠtefko Miklavič, Primož Potočnik, Steve Wilson, 2008, original scientific article Abstract: A cycle decomposition of a graph ▫$\Gamma$▫ is a set ▫$\mathcal{C}$▫ of cycles of ▫$\Gamma$▫ such that every edge of ▫$\Gamma$▫ belongs to exactly one cycle in ▫$\mathcal{C}$▫. Such a decomposition is called arc-transitive if the group of automorphisms of ▫$\Gamma$▫ that preserve setwise acts transitively on the arcs of ▫$\Gamma$▫. In this paper, we study arc-transitive cycle decompositions of tetravalent graphs. In particular, we are interested in determining and enumerating arc-transitive cycle decompositions admitted by a given arc-transitive tetravalent graph. Among other results we show that a connected tetravalent arc-transitive graph is either 2-arc-transitive, or is isomorphic to the medial graph of a reflexible map, or admits exactly one cycle structure.
Keywords: mathematics, graph theory, cycle decomposition, automorphism group, consistent cycle, medial maps
Published in RUP: 15.10.2013; Views: 6937; Downloads: 91
Link to full text |
19. |
20. Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groupsŠtefko Miklavič, Primož Šparl, 2012, original scientific article Abstract: In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph ▫$\Gamma$▫ is ▫$n$▫-HC-extendable if it contains a path of length ▫$n$▫ and if every such path is contained in some Hamilton cycle of ▫$\Gamma$▫. Similarly, ▫$\Gamma$▫ is weakly ▫$n$▫-HP-extendable if it contains a path of length ▫$n$▫ and if every such path is contained in some Hamilton path of ▫$\Gamma$▫. Moreover, ▫$\Gamma$▫ is strongly ▫$n$▫-HP-extendable if it contains a path of length ▫$n$▫ and if for every such path $P$ there is a Hamilton path of ▫$\Gamma$▫ starting with ▫$P$▫. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2-HC-extendable and a complete classification of 3-HC-extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4-HP-extendable.
Keywords: graph theory, Hamilton cycle, Hamilton path, n-HC-extendable, strongly n-HP-extendable, weakly n-HP-extendable, Cayley graph, abelian group
Published in RUP: 15.10.2013; Views: 4527; Downloads: 159
Link to full text |
