1. Tetravalent distance magic graphs of small order and an infinite family of examplesKsenija Rozman, Primož Šparl, 2025, izvirni znanstveni članek Opis: A graph of order ▫$n$▫ is distance magic if it admits a bijective labeling of its vertices with integers from ▫$1$▫ to ▫$n$▫ such that each vertex has the same sum of the labels of its neighbors. This paper contributes to the long term project of characterizing all tetravalent distance magic graphs. With the help of a computer we find that out of almost nine million connected tetravalent graphs up to order 16 only nine are distance magic. In fact, besides the six well known wreath graphs there are only three other examples, one of each of the orders 12, 14 and 16. We introduce a generalization of wreath graphs, the so-called quasi wreath graphs, and classify all distance magic graphs among them. This way we obtain infinitely many new tetravalent distance magic graphs. Moreover, the two non-wreath graphs of orders 12 and 14 are quasi wreath graphs while the one of order 16 can be obtained from a quasi wreath graph of order 14 using a simple construction due to Kovář, Fronček and Kovářová.
Ključne besede: distance magic, tetravalent, quasi wreath graph
Objavljeno v RUP: 10.09.2025; Ogledov: 972; Prenosov: 33
 Celotno besedilo (457,53 KB) |
2. On the proper interval completion problem within some chordal subclassesFrançois Dross, Claire Hilaire, Ivo Koch, Valeria Alejandra Leoni, Nina Pardal, María Inés Lopez Pujato, Vinicius Fernandes dos Santos, 2025, izvirni znanstveni članek Opis: Given a property (graph class) Π, a graph G, and an integer k, the Π-completion problem consists of deciding whether we can turn G into a graph with the property Π by adding at most k edges to G. The Π-completion problem is known to be NP-hard for general graphs when Π is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem within different subclasses of chordal graphs. We show that the problem remains NP-complete even when restricted to split graphs. We then turn our attention to positive results and present polynomial time algorithms to solve the PIG-completion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasi-threshold graphs, which provides a lower bound for the PIG-completion problem within this graph class.
Ključne besede: proper interval completion, split graph, threshold graph, quasi-threshold graph, caterpillar
Objavljeno v RUP: 06.08.2025; Ogledov: 875; Prenosov: 10
Celotno besedilo (824,75 KB)
Gradivo ima več datotek! Več... |
3. |
4. Quasi-semiregular automorphisms of cubic and tetravalent arc-transitive graphs : Group Action and Combinatorial Structures, Nankai University, Tianjin, China, 15. - 18. 6. 2018István Kovács, Yan-Quan Feng, Ademir Hujdurović, Klavdija Kutnar, Dragan Marušič, 2018, prispevek na konferenci brez natisa Ključne besede: quasi-semiregular automorphism, cubic graph, tetravalent graph, arc-transitive graph
Objavljeno v RUP: 06.12.2018; Ogledov: 4192; Prenosov: 142
 Povezava na celotno besedilo |
5. |
6. Algebraični aspekti teorije grafov : doktorska disertacijaAdemir Hujdurović, 2013, doktorska disertacija Ključne besede: circulant, bicirculant, semiregular automorphism, vertex-transitive graph, half-arc-transitive graph, snark, Cayley graph, quasi m-Cayley graph, generalized Cayley graph, I-regular action, regular cover of a graph, automorphism group
Objavljeno v RUP: 10.07.2015; Ogledov: 7052; Prenosov: 57
Povezava na celotno besedilo |
7. Quasi m-Cayley circulantsAdemir Hujdurović, 2013, objavljeni znanstveni prispevek na konferenci Opis: A graph ▫$\Gamma$▫ is called a quasi ▫$m$▫-Cayley graph on a group ▫$G$▫ if there exists a vertex ▫$\infty \in V(\Gamma)$▫ and a subgroup ▫$G$▫ of the vertex stabilizer ▫$\text{Aut}(\Gamma)_\infty$▫ of the vertex ▫$\infty$▫ in the full automorphism group ▫$\text{Aut}(\Gamma)$▫ of ▫$\Gamma$▫, such that ▫$G$▫ acts semiregularly on ▫$V(\Gamma) \setminus \{\infty\}$▫ with ▫$m$▫ orbits. If the vertex ▫$\infty$▫ is adjacent to only one orbit of ▫$G$▫ on ▫$V(\Gamma) \setminus \{\infty\}$▫, then ▫$\Gamma$▫ is called a strongly quasi ▫$m$▫-Cayley graph on ▫$G$▫ .In this paper complete classifications of quasi 2-Cayley, quasi 3-Cayley and strongly quasi 4-Cayley connected circulants are given.
Ključne besede: arc-transitive, circulant, quasi m-Cayley graph
Objavljeno v RUP: 15.10.2013; Ogledov: 5483; Prenosov: 125
Celotno besedilo (250,35 KB) |
