1. On a generalization of median graphs: k-median graphsMarc Hellmuth, Sandhya Thekkumpadan Puthiyaveedu, 2025, izvirni znanstveni članek Opis: Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. To be more formal, a graph G is a median graph if, for all μ, u, v ∈ V(G), it holds that |I(μ, u) ∩ I(μ, v) ∩ I(u, v)| = 1 where I(x, y) denotes the set of all vertices that lie on shortest paths connecting x and y.
In this paper we are interested in a natural generalization of median graphs, called k-median graphs. A graph G is a k-median graph, if there are k vertices μ1, …, μk ∈ V(G) such that, for all u, v ∈ V(G), it holds that |I(μ_i, u) ∩ I(μ_i, v) ∩ I(u, v)| = 1, 1 ≤ i ≤ k. By definition, every median graph with n vertices is an n-median graph. We provide several characterizations of k-median graphs that, in turn, are used to provide many novel characterizations of median graphs.
Ključne besede: median graph, convexity, meshed and quadrangle property, modular, interval
Objavljeno v RUP: 22.10.2025; Ogledov: 159; Prenosov: 0
 Celotno besedilo (520,78 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: 336; Prenosov: 6
Celotno besedilo (824,75 KB)
Gradivo ima več datotek! Več... |
3. Parallelizing an algorithm to find the maximal clique on interval graphs on graphical processing unitsChristian Trefftz, Andrés Santamaría-Galvis, Roberto Cruz Rodes, 2014, objavljeni znanstveni prispevek na konferenci Ključne besede: graph theory, graphics processing units, parallel algorithms, CUDA, Thrust library, interval graphs, maximal clique
Objavljeno v RUP: 18.10.2021; Ogledov: 2502; Prenosov: 25
 Povezava na celotno besedilo |
4. |
5. |
6. Nove karakterizacije v strukturni teoriji grafov : 1-popolno usmerljivi grafi, produktni grafi in cena povezanostiTatiana Romina Hartinger, 2017, doktorska disertacija Ključne besede: 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
Objavljeno v RUP: 09.11.2017; Ogledov: 5219; Prenosov: 44
Povezava na celotno besedilo |
