Source author record

Tilen Marc

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs

It was recently pointed out that certain SiO $_2$ layer structures and SiO $_2$ nanotubes can be described as full subdivisions aka subdivision graphs of partial cubes. A key tool for analyzing distance-based topological indices in molecular graphs is the Djoković-Winkler relation $Θ$ and its transitive closure $Θ^\ast$ . In this paper we study the behavior of $Θ$ and $Θ^\ast$ with respect to full subdivisions. We apply our results to describe $Θ^\ast$ in full subdivisions of fullerenes, plane triangulations, and chordal graphs.

preprint2016arXiv

Classification of vertex-transitive cubic partial cubes

Partial cubes are graphs isometrically embeddable into hypercubes. In this paper it is proved that every cubic, vertex-transitive partial cube is isomorphic to one of the following graphs: $K_2 \, \square \, C_{2n}$ , for some $n\geq 2$ , the generalized Petersen graph $G(10,3)$ , the cubic permutahedron, the truncated cuboctahedron, or the truncated icosidodecahedron. This classification is a generalization of results of Brešar et al.~from 2004 on cubic mirror graphs, it includes all cubic, distance-regular partial cubes (Weichsel, 1992), and presents a contribution to the classification of all cubic partial cubes.

preprint2016arXiv

Mirror graphs: graph theoretical characterization of reflection arrangements and finite Coxeter groups

Mirror graphs were introduced by Brešar et al. in 2004 as an intriguing class of graphs: vertex-transitive, isometrically embeddable into hypercubes, having a strong connection with regular maps and polytope structure. In this article we settle the structure of mirror graphs by characterizing them as precisely the Cayley graphs of the finite Coxeter groups or equivalently the tope graphs of reflection arrangements - well understood and classified structures. We provide a polynomial algorithm for their recognition.

preprint2016arXiv

There are no finite partial cubes of girth more than 6 and minimum degree at least 3

Partial cubes are graphs isometrically embeddable into hypercubes. We analyze how isometric cycles in partial cubes behave and derive that every partial cube of girth more than 6 must have vertices of degree less than 3. As a direct corollary we get that every regular partial cube of girth more than 6 is an even cycle. Along the way we prove that every partial cube $G$ with girth more than 6 is a tree-zone graph and therefore $2n(G)-m(G)-i(G)+ce(G)=2$ holds, where $i(G)$ is the isometric dimension of $G$ and $ce(G)$ its convex excess.

preprint2016arXiv

There is no (95,40,12,20) strongly regular graph

We show that there is no $(95,40,12,20)$ strongly regular graph and, consequently, there is no $(96,45,24,18)$ strongly regular graph, no two-graph on $96$ vertices, and no partial geometry $\rm{pg}(5,9,3)$ . The main idea of the result is based on the star complement technique and requires a small amount of computation.

preprint2014arXiv

On the Cartesian Skeleton and the Factorization of the Strong Product of Digraphs

The three standard products (the Cartesian, the direct and the strong product) of undirected graphs have been wellinvestigated, unique prime factor decomposition (PFD) are known and polynomial time algorithms have been established for determining the prime factors. For directed graphs, unique PFD results with respect to the standard products are known. However, there is still a lack of algorithms, that computes the PFD of directed graphs with respect to the direct and the strong product in general. In this contribution, we focus on the algorithmic aspects for determining the PFD of directed graphs with respect to the strong product. Essential for computing the prime factors is the construction of a so-called Cartesian skeleton. This article introduces the notion of the Cartesian skeleton of directed graphs as a generalization of the Cartesian skeleton of undirected graphs. We provide new, fast and transparent algorithms for its construction. Moreover, we present a first polynomial time algorithm for determining the PFD with respect to the strong product of arbitrary connected digraphs.

preprint2014arXiv

The Relaxed Square Property

Graph products are characterized by the existence of non-trivial equivalence relations on the edge set of a graph that satisfy a so-called square property. We investigate here a generalization, termed RSP-relations. The class of graphs with non-trivial RSP-relations in particular includes graph bundles. Furthermore, RSP-relations are intimately related with covering graph constructions. For K_23-free graphs finest RSP-relations can be computed in polynomial-time. In general, however, they are not unique and their number may even grow exponentially. They behave well for graph products, however, in sense that a finest RSP-relations can be obtained easily from finest RSP-relations on the prime factors.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Tilen Marc

Research overview

Is this your work?

7 publications

On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs

Classification of vertex-transitive cubic partial cubes

Mirror graphs: graph theoretical characterization of reflection arrangements and finite Coxeter groups

There are no finite partial cubes of girth more than 6 and minimum degree at least 3

There is no (95,40,12,20) strongly regular graph

On the Cartesian Skeleton and the Factorization of the Strong Product of Digraphs

The Relaxed Square Property

See the researcher in context

Building this map preview