Search results for "Pseudoforest"

showing 2 items of 2 documents

Highly irregular graphs with extreme numbers of edges

1997

Abstract A simple connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we find: (1) the greatest number of edges of a highly irregular graph with n vertices, where n is an odd integer (for n even this number is given in [1]), (2) the smallest number of edges of a highly irregular graph of given order.

Discrete mathematicsPseudoforestHighly irregular graphEdge-graceful labelingTheoretical Computer ScienceHypercube graphCombinatoricsCycle graphDiscrete Mathematics and CombinatoricsPath graphMultiple edgesComplement graphMathematicsofComputing_DISCRETEMATHEMATICSMathematicsDiscrete Mathematics
researchProduct

A Constructive Arboricity Approximation Scheme

2020

The arboricity \(\varGamma \) of a graph is the minimum number of forests its edge set can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they approximate the arboricity as a value without computing a corresponding forest partition. This is because they operate on pseudoforest partitions or the dual problem of finding dense subgraphs.

PseudoforestArboricityApproximation algorithm0102 computer and information sciences02 engineering and technology01 natural sciencesConstructiveCombinatoricsSet (abstract data type)Computer Science::Discrete Mathematics010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringGraph (abstract data type)Partition (number theory)020201 artificial intelligence & image processingMatroid partitioningComputer Science::Data Structures and AlgorithmsGeneralLiterature_REFERENCE(e.g.dictionariesencyclopediasglossaries)Computer Science::Distributed Parallel and Cluster ComputingMathematicsofComputing_DISCRETEMATHEMATICSMathematics
researchProduct