Back to Search
Start Over
Use the K-Neighborhood Subgraphs to Compute Canonical Labelings of Graphs
- Source :
- Mathematics, Vol 7, Iss 8, p 690 (2019), Mathematics, Volume 7, Issue 8
- Publication Year :
- 2019
- Publisher :
- MDPI AG, 2019.
-
Abstract
- This paper puts forward an innovative theory and method to calculate the canonical labelings of graphs that are distinct to N a u t y &rsquo<br />s. It shows the correlation between the canonical labeling of a graph and the canonical labeling of its complement graph. It regularly examines the link between computing the canonical labeling of a graph and the canonical labeling of its o p e n k-n e i g h b o r h o o d s u b g r a p h. It defines d i f f u s i o n d e g r e e s e q u e n c e s and e n t i r e d i f f u s i o n d e g r e e s e q u e n c e. For each node of a graph G, it designs a characteristic m _ N e a r e s t N o d e to improve the precision for calculating canonical labeling. Two theorems established here display how to compute the first nodes of M a x Q ( G ) . Another theorem presents how to determine the second nodes of M a x Q ( G ) . When computing C m a x ( G ) , if M a x Q ( G ) already holds the first i nodes u 1 , u 2 , ⋯ , u i , Diffusion and Nearest Node theorems provide skill on how to pick the succeeding node of M a x Q ( G ) . Further, it also establishes two theorems to determine the C m a x ( G ) of disconnected graphs. Four algorithms implemented here demonstrate how to compute M a x Q ( G ) of a graph. From the results of the software experiment, the accuracy of our algorithms is preliminarily confirmed. Our method can be employed to mine the frequent subgraph. We also conjecture that if there is a node v &isin<br />S ( G ) meeting conditions C m a x ( G - v ) ⩽ C m a x ( G - w ) for each w &isin<br />S ( G ) &and<br />w &ne<br />v , then u 1 = v for M a x Q ( G ) .
- Subjects :
- adjacency matrix
General Mathematics
MathematicsofComputing_GENERAL
open k-neighborhood subgraph
01 natural sciences
Combinatorics
diffusion degree sequence
0502 economics and business
Computer Science (miscellaneous)
Data_FILES
Adjacency matrix
canonical labeling
0101 mathematics
Engineering (miscellaneous)
Complement graph
Physics
050208 finance
Conjecture
algorithm
lcsh:Mathematics
010102 general mathematics
05 social sciences
entire diffusion degree sequences
lcsh:QA1-939
Graph
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Software_PROGRAMMINGLANGUAGES
Subjects
Details
- Language :
- English
- ISSN :
- 22277390
- Volume :
- 7
- Issue :
- 8
- Database :
- OpenAIRE
- Journal :
- Mathematics
- Accession number :
- edsair.doi.dedup.....8dcef060ea9bec495bc441910c31ac9d