Black-and-white threshold graphs

Details Black-and-white threshold graphs Black-and-white threshold graphs

2011-04-20

arxiv.org/abs/1104.3917v1

Mathematics

Combinatorics

Scientific paper

Let k be a natural number. We introduce k-threshold graphs. We show that there exists an O(n^3) algorithm for the recognition of k-threshold graphs for each natural number k. k-Threshold graphs are characterized by a finite collection of forbidden induced subgraphs. For the case k=2 we characterize the partitioned 2-threshold graphs by forbidden induced subgraphs. We introduce restricted -, and special 2-threshold graphs. We characterize both classes by forbidden induced subgraphs. The restricted 2-threshold graphs coincide with the switching class of threshold graphs. This provides a decomposition theorem for the switching class of threshold graphs.

Affiliated with

Also associated with

No associations

Rating

Black-and-white threshold graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Black-and-white threshold graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Black-and-white threshold graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-431766