Source author record

Carsten Thomassen

Carsten Thomassen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Information Theory math.IT

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2020arXiv

Locally Hamiltonian graphs and minimal size of maximal graphs on a surface

We prove that every locally Hamiltonian graph with $n\ge 3$ vertices and possibly with multiple edges has at least $3n-6$ edges with equality if and only if it triangulates the sphere. As a consequence, every edge-maximal embedding of a graph $G$ graph on some 2-dimensional surface $Σ$ (not necessarily compact) has at least $3n-6$ edges with equality if and only if $G$ also triangulates the sphere. If, in addition, $G$ is simple, then for each vertex $v$, the cyclic ordering of the edges around $v$ on $Σ$ is the same as the clockwise or anti-clockwise orientation around $v$ on the sphere. If $G$ contains no complete graph on 4 vertices and has at least 4 vertices, then the face-boundaries are the same in the two embeddings.

preprint2020arXiv

Partite Turán-densities for complete $r-$uniform hypergraphs on $r+1$ vertices

In this paper we investigate density conditions for finding a complete $r$-uniform hypergraph $K_{r+1}^{(r)}$ on $r+1$ vertices in an $(r+1)$-partite $r$-uniform hypergraph $G$. First we prove an optimal condition in terms of the densities of the $(r+1)$ induced $r$-partite subgraphs of $G$. Second, we prove a version of this result where we assume that $r$-tuples of vertices in $G$ have their neighbours evenly distributed in $G$. Third, we also prove a counting result for the minimum number of copies of $K_{r+1}^{(r)}$ when $G$ satisfies our density bound, and present some open problems. A striking difference between the graph, $r=2$, and the hypergraph, $ r \geq 3 $, cases is that in the first case both the existence threshold and the counting function are non-linear in the involved densities, whereas for hypergraphs they are given by a linear function. Also, the smallest density of the $r$-partite parts needed to ensure the existence of a complete $r$-graph with $(r+1)$ vertices is equal to the golden ratio $τ=0.618\ldots$ for $r=2$, while it is $\frac{r}{r+1}$for $r\geq3$.

preprint2016arXiv

Decomposing graphs into a constant number of locally irregular subgraphs

A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index $χ_{\rm irr}'(G)$ of a graph $G$ is the smallest number of locally irregular subgraphs needed to edge-decompose $G$. Not all graphs have such a decomposition, but Baudon, Bensmail, Przybyło, and Woźniak conjectured that if $G$ can be decomposed into locally irregular subgraphs, then $χ_{\rm irr}'(G)\leq 3$. In support of this conjecture, Przybyło showed that $χ_{\rm irr}'(G)\leq 3$ holds whenever $G$ has minimum degree at least $10^{10}$. Here we prove that every bipartite graph $G$ which is not an odd length path satisfies $χ_{\rm irr}'(G)\leq 10$. This is the first general constant upper bound on the irregular chromatic index of bipartite graphs. Combining this result with Przybyło's result, we show that $χ_{\rm irr}'(G) \leq 328$ for every graph $G$ which admits a decomposition into locally irregular subgraphs. Finally, we show that $χ_{\rm irr}'(G)\leq 2$ for every $16$-edge-connected bipartite graph $G$.

preprint2012arXiv

The maximum number of minimal codewords in long codes

Upper bounds on the maximum number of minimal codewords in a binary code follow from the theory of matroids. Random coding provide lower bounds. In this paper we compare these bounds with analogous bounds for the cycle code of graphs. This problem (in the graphic case) was considered in 1981 by Entringer and Slater who asked if a connected graph with $p$ vertices and $q$ edges can have only slightly more that $2^{q-p}$ cycles. The bounds in this note answer this in the affirmative for all graphs except possibly some that have fewer than $2p+3\log_2(3p)$ edges. We also conclude that an Eulerian (even) graph has at most $2^{q-p}$ cycles unless the graph is a subdivision of a 4-regular graph that is the edge-disjoint union of two Hamiltonian cycles, in which case it may have as many as $2^{q-p}+p$ cycles.