pith. sign in

arxiv: 1601.01365 · v1 · pith:573NB5HQnew · submitted 2016-01-07 · 🧮 math.CO

Properties of Catlin's reduced graphs and supereulerian graphs

classification 🧮 math.CO
keywords graphscollapsiblegraphreducedsubgraphsnontrivialpropertiesspanning
0
0 comments X
read the original abstract

A graph $G$ is called collapsible if for every even subset $R\subseteq V(G)$, there is a spanning connected subgraph $H$ of $G$ such that $R$ is the set of vertices of odd degree in $H$. A graph is the reduction of $G$ if it is obtained from $G$ by contracting all the nontrivial collapsible subgraphs. A graph is reduced if it has no nontrivial collapsible subgraphs. In this paper, we first prove a few results on the properties of reduced graphs. As an application, for 3-edge-connected graphs $G$ of order $n$ with $d(u)+d(v)\ge 2(n/p-1)$ for any $uv\in E(G)$ where $p>0$ are given, we show how such graphs change if they have no spanning Eulerian subgraphs when $p$ is increased from $p=1$ to 10 then to $15$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.