Cycles and components in geometric graphs: adjacency operator approach

René Schott (1, 2) , Stacey Staples (3)

1 IECN - Institut Élie Cartan de Nancy
2 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 Department of Mathematics and Statistics - Southern Illinois University

Nilpotent and idempotent adjacency operator methods are applied to the study of random geometric graphs in a discretized, $d$-dimensional unit cube$[0; 1]$^d. Cycles are enumerated, sizes of maximal connected compo- nents are computed, and closed formulas are obtained for graph circumfer- ence and girth. Expected numbers of $k$-cycles, expected sizes of maximal components, and expected circumference and girth are also computed by considering powers of adjacency operators.

Domaines: Probabilités [math.PR]

René Schott, Stacey Staples. Cycles and components in geometric graphs: adjacency operator approach. 2009. ⟨hal-00386999⟩