On the distribution of the domination number for random class cover catch digraphs

DOI10.1016/s0167-7152(01)00129-8zbMath0999.05082MaRDI QIDQ158221

Carey E. Priebe, Jason G. Devinney, David J. Marchette, David J. Marchette, Carey E. Priebe, Jason G. DeVinney

Publication date: December 2001

Published in: Statistics & Probability Letters, Statistics \& Probability Letters (Search for Journal in Brave)

zbMATH Keywords

distribution; domination number; intersection digraphs; random interval catch digraphs

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60C05: Combinatorial probability

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C20: Directed graphs (digraphs), tournaments

Related Items

A new family of random graphs for testing spatial segregation, GEOMETRIC PROXIMITY GRAPHS FOR IMPROVING NEAREST NEIGHBOR METHODS IN INSTANCE-BASED LEARNING AND DATA MINING, rcccd, A general SLLN for the one-dimensional class cover problem, Class cover catch digraphs for latent class discovery in gene expression monitoring by DNA microarrays, Relative density of the random \(R\)-factor proximity catch digraph for testing spatial patterns of segregation and association, The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data, A CLT for a one-dimensional class cover problem, Characterizing the scale dimension of a high-dimensional classification problem, A SLLN for a one-dimensional class cover problem, A new family of proximity graphs: class cover catch digraphs, The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association

Cites Work

• A characterization of interval catch digraphs
• Analysis of a greedy heuristic for finding small dominating sets in graphs
• Approximation algorithms for combinatorial problems
• Algorithms for interval catch digraphs
• Inequalities for minimal covering sets in set systems of given rank
• Approximation algorithms for the class cover problem
• Interval digraphs: An analogue of interval graphs
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Topics in Intersection Graph Theory
• On Random Intersection Graphs: The Subgraph Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item