Decomposing a Graph into Unigraphs

MaRDI QIDQ6317509zbMATH OpenFDO

Authors Takashi Horiyama, Jun Kawahara, Shin-Ichi Minato, Yu Nakahata

Publication date 20 April 2019

Abstract: Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. There are many subclasses of unigraphs such as threshold graphs, split matrogenic graphs, matroidal graphs, and matrogenic graphs. Unigraphs and these subclasses are well studied in the literature. Nevertheless, there are few results on superclasses of unigraphs. In this paper, we introduce two types of generalizations of unigraphs: $k$-unigraphs and $k$-strong unigraphs. We say that a graph $G$ is a $k$-unigraph if $G$ can be partitioned into $k$ unigraphs. $G$ is a $k$-strong unigraph if not only each subgraph is a unigraph but also the whole graph can be uniquely determined up to isomorphism, by using the degree sequences of all the subgraphs in the partition. We describe a relation between $k$-strong unigraphs and the subgraph isomorphism problem. We show some properties of $k$-(strong) unigraphs and algorithmic results on calculating the minimum $k$ such that a graph $G$ is a $k$-(strong) unigraph. This paper will open many other research topics.

This page was built for publication: Decomposing a Graph into Unigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6317509)