isGraphical: Test if a degree sequence isGraphical

In mbojan/mbtools: Chaotic Collection of Functions and Datasets Possibly Useful Also To Others

Test if a degree sequence isGraphical

Description

Given a vector of integer values check whether it is graphical, i.e. whether there exists an undirected graph with a corresponding degree sequence.

Usage

isGraphical(x, method = c("tv", "eg"))

Arguments

x	integer vector, degree sequence to be tested
method	character, type of algorithm to be used, defaults to "tv", see Details

Details

A sequence of non-negative integers a_1, a_2, ..., a_p. is graphical if there exists a graph with the corresponding degree sequence.

This function takes such a sequence as an argument x and performes the check.

Two algorithms are implemented. The first one due too Erdos and Gallai (1960), the second, a bit more efficient and the default, is due too Tripathi and Vijay (2003). The method can be selected with the method argument.

Value

Logical, whether the sequence is graphical or not.

References

P. Erdos, T. Gallai (1960) Graphs with prescribed degree of vertices (Hungarian), Mat. Lapok 11 264–274.

A. Tripathi and Sujith Vijay (2003) A note on a theorem of Erdos and Gallai, Discrete Mathematics 265 417–420

Examples

### Test both methods on some simple graphs
testit <- function(d)
{
    rval <- c( eg = isGraphical(d, "eg"),
        tv = isGraphical(d, "tv") )
    if(!all(rval))
    {
        print(rval)
        stop("failed")
    }
    rval
}
# graphs of size 3
testit( c(0,0,0) )
testit( c(0,1,1) )
testit( c(1,2,1) )
testit( c(2,2,2) )

mbojan/mbtools documentation built on Oct. 16, 2023, 8:18 p.m.