Lupa

Search the repository Help

A- | A+ | Print
Query: search in
search in
search in
search in
* old and bolonia study programme

Options:
  Reset


1 - 9 / 9
First pagePrevious page1Next pageLast page
1.
On the connectivity of bipartite distance-balanced graphs
Štefko Miklavič, Primož Šparl, 2012, original scientific article

Abstract: A connected graph ▫$\varGamma$▫ is said to be distance-balanced whenever for any pair of adjacent vertices ▫$u,v$▫ of ▫$\varGamma$▫ the number of vertices closer to ▫$u$▫ than to ▫$v$▫ is equal to the number of vertices closer to ▫$v$▫ than to ▫$u$▫. In [K. Handa, Bipartite graphs with balanced ▫$(a,b)$▫-partitions, Ars Combin. 51 (1999), 113-119] Handa asked whether every bipartite distance-balanced graph, that is not a cycle, is 3-connected. In this paper the Handa question is answered in the negative. Moreover, we show that a minimal bipartite distance-balanced graph, that is not a cycle and is not 3-connected, has 18 vertices and is unique. In addition, we give a complete classification of non-3-connected bipartite distance-balanced graphs for which the minimal distance between two vertices in a 2-cut is three. All such graphs are regular and for each ▫$k \geq 3$▫ there exists an infinite family of such graphs which are ▫$k$▫-regular.Furthermore, we determine a number of structural properties that a bipartite distance-balanced graph, which is not 3-connected, must have. As an application, we give a positive answer to the Handa question for the subfamily of bipartite strongly distance-balanced graphs.
Found in: ključnih besedah
Summary of found: Zadetek v naslovu
Keywords: graph theory, connected graphs, connectivity, distance-balanced graphs, bipartite graphs
Published: 15.10.2013; Views: 1346; Downloads: 50
URL Full text (0,00 KB)

2.
Maximum genus, connectivity, and Nebeský's theorem
Martin Škoviera, Roman Nedela, Dan Steven Archdeacon, Michal Kotrbčík, 2015, original scientific article

Found in: ključnih besedah
Summary of found: Zadetek v naslovu
Keywords: maksimalen rod, Nebeskýnov rod, Bettijevo število, povezanost, maximum genus, Nebeský theorem, Betti number, connectivity
Published: 15.10.2015; Views: 1083; Downloads: 68
URL Full text (0,00 KB)

3.
Vector connectivity in graphs
Ferdinando Cicalese, Martin Milanič, Pinar Heggernes, Endre Boros, Pim Van 't Hof, Romeo Rizzi, 2014, published scientific conference contribution abstract (invited lecture)

Found in: ključnih besedah
Summary of found: Zadetek v naslovu
Keywords: vektorska povezanost, aproksimacijski algoritmi, polinomski algoritmi, NP-poln problem, razcepljeni grafi, kografi, drevesa, vector connectivity, approximation algorithms, poynomial time algorithms, NP-hard problem, split graphs, cographs, trees
Published: 15.10.2015; Views: 1315; Downloads: 96
URL Full text (0,00 KB)
This document has more files! More...

4.
On cyclic edge-connectivity of fullerenes
Dragan Marušič, Klavdija Kutnar, 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$▫.
Found in: ključnih besedah
Summary of found: Zadetek v naslovu
Keywords: graph, fullerene graph, cyclic edge-connectivity, hamilton cycle, perfect matching
Published: 03.04.2017; Views: 705; Downloads: 83
URL Full text (0,00 KB)

5.
On the complexity of the vector connectivity problem
Ferdinando Cicalese, Martin Milanič, Romeo Rizzi, 2015, original scientific article

Found in: ključnih besedah
Summary of found: Zadetek v naslovu
Keywords: vector connectivity, APX-hardness, NP-hardness, polynomial-time algorithm, block graphs
Published: 03.04.2017; Views: 622; Downloads: 22
URL Full text (0,00 KB)

6.
The price of connectivity for cycle transversals
Tatiana R. Hartinger, Matthew Johnson, Martin Milanič, Daniël Paulusma, 2015, published scientific conference contribution

Found in: ključnih besedah
Summary of found: Zadetek v naslovu
Keywords: price of connectivity, hereditary graph class, path, cycle, transversal
Published: 08.08.2016; Views: 1375; Downloads: 40
URL Full text (0,00 KB)

7.
The price of connectivity for cycle transversals
Tatiana R. Hartinger, Matthew Johnson, Martin Milanič, Daniël Paulusma, 2016, original scientific article

Found in: ključnih besedah
Summary of found: Zadetek v naslovu
Keywords: price of connectivity, hereditary graph class, path, cycle, transversal
Published: 08.08.2016; Views: 838; Downloads: 36
URL Full text (0,00 KB)

8.
Nove karakterizacije v strukturni teoriji grafov
Tatiana Romina Hartinger, 2017, doctoral dissertation

Found in: ključnih besedah
Summary of found: ...product, direct product, strong product, price of connectivity, cycle transversal, path transversal...
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: 09.11.2017; Views: 580; Downloads: 10
URL Full text (0,00 KB)

9.
Aproksimacijski vidiki vektorske dominacije in vektorske povezanosti v grah
Mirza Krbezlija, 2018, undergraduate thesis

Found in: ključnih besedah
Summary of found: ...graph, vector domination, vector connectivity, submodular set covering problem, approximation algorithm, greedy...
Keywords: graph, vector domination, vector connectivity, submodular set covering problem, approximation algorithm, greedy heuristic, integer linear programming
Published: 17.09.2018; Views: 330; Downloads: 11
URL Full text (0,00 KB)

Search done in 0 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica