On the Distribution of the Domination Number of a New Family of Parametrized Random Digraphs

zbMATH Open1127.05092arXiv0802.0617MaRDI QIDQ5423736FDOQ5423736

Authors: Elvan Ceyhan, Carey E. Priebe 

Publication date: 31 October 2007

Abstract: We derive the asymptotic distribution of the domination number of a new family of random digraph called proximity catch digraph (PCD), which has application to statistical testing of spatial point patterns and to pattern recognition. The PCD we use is a parametrized digraph based on two sets of points on the plane, where sample size and locations of the elements of one is held fixed, while the sample size of the other whose elements are randomly distributed over a region of interest goes to infinity. PCDs are constructed based on the relative allocation of the random set of points with respect to the Delaunay triangulation of the other set whose size and locations are fixed. We introduce various auxiliary tools and concepts for the derivation of the asymptotic distribution. We investigate these concepts in one Delaunay triangle on the plane, and then extend them to the multiple triangle case. The methods are illustrated for planar data, but are applicable in higher dimensions also.

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

Recommendations

• A note on domination parameters in random graphs
• On the domination number of a random graph
• On the distribution of the domination number for random class cover catch digraphs
• On the concentration of the domination number of the random graph
• New probabilistic upper bounds on the domination number of a graph
• The domination number of a random graph
• scientific article; zbMATH DE number 2089976
• scientific article; zbMATH DE number 5532162
• An investigation of new graph invariants related to the domination number of random proximity catch digraphs

zbMATH Keywords

domination numberDelaunay triangulationproximity mapRandom graphproximity catch digraph

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random graphs (graph-theoretic aspects) (05C80) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial probability (60C05)

Cited In (12)

• Spatial clustering tests based on the domination number of a new random digraph family
• A note on domination parameters in random graphs
• Domination number of an interval catch digraph family and its use for testing uniformity
• The distribution of the relative arc density of a family of interval catch digraph based on uniform data
• The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association
• Extension of one-dimensional proximity regions to higher dimensions
• An investigation of new graph invariants related to the domination number of random proximity catch digraphs
• A new family of random graphs for testing spatial segregation
• On the distribution of the domination number for random class cover catch digraphs
• A general SLLN for the one-dimensional class cover problem
• A CLT for a one-dimensional class cover problem
• The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data

This page was built for publication: On the Distribution of the Domination Number of a New Family of Parametrized Random Digraphs

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