Lupa

Search the repository Help

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

Options:
  Reset


1 - 5 / 5
First pagePrevious page1Next pageLast page
1.
2.
3.
Vertex cover at distance on H-free graphs
Clément Jean Dallard, Mirza Krbezlija, Martin Milanič, 2021, published scientific conference contribution

Keywords: distance-k vertex cover, H-free graph, np-completeness, polynomial-time algorithm, dichotomy
Published in RUP: 16.07.2021; Views: 1359; Downloads: 30
URL Link to full text

4.
Distance-transitive graphs admit semiregular automorphisms
Klavdija Kutnar, Primož Šparl, 2010, original scientific article

Abstract: A distance-transitive graph is a graph in which for every two ordered pairs ofvertices ▫$(u,v)$▫ and ▫$(u',v')$▫ such that the distance between ▫$u$▫ and ▫$v$▫ is equal to the distance between ▫$u'$▫ and ▫$v'$▫ there exists an automorphism of the graph mapping ▫$u$▫ to ▫$u'$▫ and ▫$v$▫ to ▫$v'$▫. A semiregular element of a permutation group is anon-identity element having all cycles of equal length in its cycle decomposition. It is shown that every distance-transitive graph admits a semiregular automorphism.
Keywords: distance-transitive graph, vertex-transitive graph, semiregular automorphism, permutation group
Published in RUP: 15.10.2013; Views: 3374; Downloads: 98
URL Link to full text

5.
Distance-balanced graphs: Symmetry conditions
Klavdija Kutnar, Aleksander Malnič, Dragan Marušič, Štefko Miklavič, 2006, original scientific article

Abstract: A graph ▫$X$▫ is said to be distance-balanced if for any edge ▫$uv$▫ of ▫$X$▫, the number of vertices closer to ▫$u$▫ than to ▫$v$▫ is equal to the number of vertices closer to ▫$v$▫ than to ▫$u$▫. A graph ▫$X$▫ is said to be strongly distance-balanced if for any edge ▫$uv$▫ of ▫$X$▫ and any integer ▫$k$▫, the number of vertices at distance ▫$k$▫ from ▫$u$▫ and at distance ▫$k+1$▫ from ▫$v$▫ is equal to the number of vertices at distance ▫$k+1$▫ from ▫$u$▫ and at distance ▫$k$▫ from ▫$v$▫. Exploring the connection between symmetry properties of graphs and the metric property of being (strongly) distance-balanced is the main theme of this article. That a vertex-transitive graph is necessarily strongly distance-balanced and thus also distance-balanced is an easy observation. With only a slight relaxation of the transitivity condition, the situation changes drastically: there are infinite families of semisymmetric graphs (that is, graphs which are edge-transitive, but not vertex-transitive) which are distance-balanced, but there are also infinite families of semisymmetric graphs which are not distance-balanced. Results on the distance-balanced property in product graphs prove helpful in obtaining these constructions. Finally, a complete classification of strongly distance-balanced graphs is given for the following infinite families of generalized Petersen graphs: GP▫$(n,2)$▫, GP▫$(5k+1,k)$▫, GP▫$(3k 3,k)$▫, and GP▫$(2k+2,k)$▫.
Keywords: graph theory, graph, distance-balanced graphs, vertex-transitive, semysimmetric, generalized Petersen graph
Published in RUP: 15.10.2013; Views: 4358; Downloads: 90
URL Link to full text

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