Spiders can be recognized by counting their legs

DOI10.1007/S11786-015-0233-1zbMATH Open1329.05069DBLPjournals/mics/BerkemerCFHHS15arXiv1411.2105OpenAlexW1600659061WikidataQ56267297 ScholiaQ56267297MaRDI QIDQ904532FDOQ904532

Authors: Sarah J. Berkemer, Ricardo R. C. Chaves, Adrian Fritz, Marc Hellmuth, Maribel Hernandez-Rosales, Peter F. Stadler 

Publication date: 13 January 2016

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Abstract: Spiders are arthropods that can be distinguished from their closest relatives, the insects, by counting their legs. Spiders have 8, insects just 6. Spider graphs are a very restricted class of graphs that naturally appear in the context of cograph editing. The vertex set of a spider (or its complement) is naturally partitioned into a clique (the body), an independent set (the legs), and a rest (serving as the head). Here we show that spiders can be recognized directly from their degree sequences through the number of their legs (vertices with degree 1). Furthermore, we completely characterize the degree sequences of spiders.

Full work available at URL: https://arxiv.org/abs/1411.2105

Recommendations

• Spiders everywhere
• Gracefulness of families of spiders
• A spanning \(k\)-spider in a graph.
• scientific article; zbMATH DE number 2038756
• Publication:3201076

zbMATH Keywords

phylogeneticsspiderdegree sequencecographP4-sparse

Mathematics Subject Classification ID

Applications of graph theory (05C90) Vertex degrees (05C07) Structural characterization of families of graphs (05C75) Other natural sciences (mathematical treatment) (92F99)

Cites Work

• Title not available (Why is that?)
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• A remark on the existence of finite graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Complexity and parameterized algorithms for cograph editing
• Orthology relations, symbolic ultrametrics, and cographs
• Cograph editing: complexity and parameterized algorithms
• Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes

This page was built for publication: Spiders can be recognized by counting their legs

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