Published in

Springer, Mathematics in Computer Science, 4(9), p. 437-441, 2015

DOI: 10.1007/s11786-015-0233-1

Links

Tools

Export citation

Search in Google Scholar

Spiders can be recognized by counting their legs

This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

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.