Source author record

Gasper Fijavz

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On minimal graphs containing k perfect matchings

We call a finite undirected graph minimally k-matchable if it has at least k distinct perfect matchings but deleting any edge results in a graph which has not. An odd subdivision of some graph G is any graph obtained by replacing every edge of G by a path of odd length connecting its end vertices such that all these paths are internally disjoint. We prove that for every k>0 there exists a finite set of graphs S(k) such that every minimally k-matchable graph is isomorphic to a disjoint union of an odd subdivision of some graph from S(k) and any number of copies of the complete graph on two vertices.

preprint2016arXiv

Threshold Colorings of Prisms and the Petersen Graph

Let $G$ be a graph, $r \geq t$ integers, and $N \subseteq E(G)$ . An $(r,t)$ -threshold-coloring of $G$ with respect to $N$ is a mapping $c: V(G) \rightarrow \{0,\ldots,r-1\}$ such that $|c(u)-c(v)| \leq t$ for every $uv \in N$ and $|c(u)-c(v)|>t$ for every $uv \in E(G) \setminus N$ . A graph is total threshold colorable if there exist integers $r,t$ such that for every $N \subseteq E(G)$ , $G$ admits an $(r,t)$ -threshold-coloring with respect to $N$ . We show that every prism is total threshold colorable, and that the Petersen graph is total threshold colorable. In contrast to this fact we show that Moebius ladders are not total threshold colorable, from which it follows that there is no characterization of being total threshold colorable in terms of a finite set of forbidden subgraphs.

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.