Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs Article Swipe

PDF

Jarek Duda ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2402.04916

While standard Weisfeiler-Leman vertex labels are not able to distinguish even vertices of regular graphs, there is proposed and tested family of inexpensive polynomial time vertex and edge invariants, distinguishing much more difficult SRGs (strongly regular graphs), also often their vertices. Among 43717 SRGs from dataset by Edward Spence, proposed vertex invariants alone were able to distinguish all but 4 pairs of graphs, which were easily distinguished by further application of proposed edge invariants. Specifically, proposed vertex invariants are traces or sorted diagonals of $(A|_{N_a})^p$ adjacency matrix $A$ restricted to $N_a$ neighborhood of vertex $a$, already for $p=3$ distinguishing all SRGs from 6 out of 13 sets in this dataset, 8 if adding $p=4$. Proposed edge invariants are analogously traces or diagonals of powers of $\bar{A}_{ab,cd}=A_{ab} A_{ac} A_{bd}$, nonzero for $(a,b)$ being edges. As SRGs are considered the most difficult cases for graph isomorphism problem, such algebraic-combinatorial invariants bring hope that this problem is polynomial time.

Related Topics

Vertex (Graph Theory)

Enhanced Data Rates For Gsm Evolution

Combinatorics

Computer Science

Mathematics

Theoretical Computer Science

Artificial Intelligence

Philosophy

Epistemology

Concepts

Simple (philosophy) Vertex (graph theory) Enhanced Data Rates for GSM Evolution Combinatorics Computer science Mathematics Theoretical computer science Graph Artificial intelligence Philosophy Epistemology

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2402.04916
PDF: https://arxiv.org/pdf/2402.04916
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4391673361

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4391673361

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2402.04916

Digital Object Identifier
Title: Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-02-07

Full publication date if available
Authors: Jarek Duda

List of authors in order
Landing page: https://arxiv.org/abs/2402.04916

Publisher landing page
PDF URL: https://arxiv.org/pdf/2402.04916

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2402.04916

Direct OA link when available
Concepts: Simple (philosophy), Vertex (graph theory), Enhanced Data Rates for GSM Evolution, Combinatorics, Computer science, Mathematics, Theoretical computer science, Graph, Artificial intelligence, Philosophy, Epistemology

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4391673361
doi	https://doi.org/10.48550/arxiv.2402.04916
ids.doi	https://doi.org/10.48550/arxiv.2402.04916
ids.openalex	https://openalex.org/W4391673361
fwci
type	preprint
title	Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T12541
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9531000256538391
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Graph Labeling and Dimension Problems
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C2780586882
concepts[0].level	2
concepts[0].score	0.7326825857162476
concepts[0].wikidata	https://www.wikidata.org/wiki/Q7520643
concepts[0].display_name	Simple (philosophy)
concepts[1].id	https://openalex.org/C80899671
concepts[1].level	3
concepts[1].score	0.6936930418014526
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1304193
concepts[1].display_name	Vertex (graph theory)
concepts[2].id	https://openalex.org/C162307627
concepts[2].level	2
concepts[2].score	0.6391351222991943
concepts[2].wikidata	https://www.wikidata.org/wiki/Q204833
concepts[2].display_name	Enhanced Data Rates for GSM Evolution
concepts[3].id	https://openalex.org/C114614502
concepts[3].level	1
concepts[3].score	0.5285148620605469
concepts[3].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[3].display_name	Combinatorics
concepts[4].id	https://openalex.org/C41008148
concepts[4].level	0
concepts[4].score	0.4406163990497589
concepts[4].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[4].display_name	Computer science
concepts[5].id	https://openalex.org/C33923547
concepts[5].level	0
concepts[5].score	0.3959292471408844
concepts[5].wikidata	https://www.wikidata.org/wiki/Q395
concepts[5].display_name	Mathematics
concepts[6].id	https://openalex.org/C80444323
concepts[6].level	1
concepts[6].score	0.32692015171051025
concepts[6].wikidata	https://www.wikidata.org/wiki/Q2878974
concepts[6].display_name	Theoretical computer science
concepts[7].id	https://openalex.org/C132525143
concepts[7].level	2
concepts[7].score	0.3054174780845642
concepts[7].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[7].display_name	Graph
concepts[8].id	https://openalex.org/C154945302
concepts[8].level	1
concepts[8].score	0.21157968044281006
concepts[8].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[8].display_name	Artificial intelligence
concepts[9].id	https://openalex.org/C138885662
concepts[9].level	0
concepts[9].score	0.05289798974990845
concepts[9].wikidata	https://www.wikidata.org/wiki/Q5891
concepts[9].display_name	Philosophy
concepts[10].id	https://openalex.org/C111472728
concepts[10].level	1
concepts[10].score	0.0
concepts[10].wikidata	https://www.wikidata.org/wiki/Q9471
concepts[10].display_name	Epistemology
keywords[0].id	https://openalex.org/keywords/simple
keywords[0].score	0.7326825857162476
keywords[0].display_name	Simple (philosophy)
keywords[1].id	https://openalex.org/keywords/vertex
keywords[1].score	0.6936930418014526
keywords[1].display_name	Vertex (graph theory)
keywords[2].id	https://openalex.org/keywords/enhanced-data-rates-for-gsm-evolution
keywords[2].score	0.6391351222991943
keywords[2].display_name	Enhanced Data Rates for GSM Evolution
keywords[3].id	https://openalex.org/keywords/combinatorics
keywords[3].score	0.5285148620605469
keywords[3].display_name	Combinatorics
keywords[4].id	https://openalex.org/keywords/computer-science
keywords[4].score	0.4406163990497589
keywords[4].display_name	Computer science
keywords[5].id	https://openalex.org/keywords/mathematics
keywords[5].score	0.3959292471408844
keywords[5].display_name	Mathematics
keywords[6].id	https://openalex.org/keywords/theoretical-computer-science
keywords[6].score	0.32692015171051025
keywords[6].display_name	Theoretical computer science
keywords[7].id	https://openalex.org/keywords/graph
keywords[7].score	0.3054174780845642
keywords[7].display_name	Graph
keywords[8].id	https://openalex.org/keywords/artificial-intelligence
keywords[8].score	0.21157968044281006
keywords[8].display_name	Artificial intelligence
keywords[9].id	https://openalex.org/keywords/philosophy
keywords[9].score	0.05289798974990845
keywords[9].display_name	Philosophy
language	en
locations[0].id	pmh:oai:arXiv.org:2402.04916
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2402.04916
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2402.04916
locations[1].id	doi:10.48550/arxiv.2402.04916
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2402.04916
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5109420627
authorships[0].author.orcid
authorships[0].author.display_name	Jarek Duda
authorships[0].author_position	first
authorships[0].raw_author_name	Duda, Jarek
authorships[0].is_corresponding	True
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2402.04916
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-02-09T00:00:00
display_name	Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T12541
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9531000256538391
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Graph Labeling and Dimension Problems
related_works	https://openalex.org/W1585007175, https://openalex.org/W2382521049, https://openalex.org/W2144385241, https://openalex.org/W2165950148, https://openalex.org/W4253593777, https://openalex.org/W2951497643, https://openalex.org/W4300101996, https://openalex.org/W3101625811, https://openalex.org/W2338854850, https://openalex.org/W2184239527
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2402.04916
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2402.04916
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2402.04916
primary_location.id	pmh:oai:arXiv.org:2402.04916
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2402.04916
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2402.04916
publication_date	2024-02-07
publication_year	2024
referenced_works_count	0
abstract_inverted_index.4	59
abstract_inverted_index.6	102
abstract_inverted_index.8	110
abstract_inverted_index.13	105
abstract_inverted_index.As	133
abstract_inverted_index.by	46, 67
abstract_inverted_index.if	111
abstract_inverted_index.in	107
abstract_inverted_index.is	16, 153
abstract_inverted_index.of	12, 21, 61, 70, 83, 92, 104, 122, 124
abstract_inverted_index.or	80, 120
abstract_inverted_index.to	8, 55, 89
abstract_inverted_index.$A$	87
abstract_inverted_index.all	57, 99
abstract_inverted_index.and	18, 26
abstract_inverted_index.are	5, 78, 117, 135
abstract_inverted_index.but	58
abstract_inverted_index.for	96, 129, 141
abstract_inverted_index.not	6
abstract_inverted_index.out	103
abstract_inverted_index.the	137
abstract_inverted_index.$a$,	94
abstract_inverted_index.SRGs	33, 43, 100, 134
abstract_inverted_index.able	7, 54
abstract_inverted_index.also	37
abstract_inverted_index.edge	27, 72, 115
abstract_inverted_index.even	10
abstract_inverted_index.from	44, 101
abstract_inverted_index.hope	149
abstract_inverted_index.more	31
abstract_inverted_index.most	138
abstract_inverted_index.much	30
abstract_inverted_index.sets	106
abstract_inverted_index.such	145
abstract_inverted_index.that	150
abstract_inverted_index.this	108, 151
abstract_inverted_index.time	24
abstract_inverted_index.were	53, 64
abstract_inverted_index.$N_a$	90
abstract_inverted_index.$p=3$	97
abstract_inverted_index.43717	42
abstract_inverted_index.Among	41
abstract_inverted_index.While	0
abstract_inverted_index.alone	52
abstract_inverted_index.being	131
abstract_inverted_index.bring	148
abstract_inverted_index.cases	140
abstract_inverted_index.graph	142
abstract_inverted_index.often	38
abstract_inverted_index.pairs	60
abstract_inverted_index.their	39
abstract_inverted_index.there	15
abstract_inverted_index.time.	155
abstract_inverted_index.which	63
abstract_inverted_index.$p=4$.	113
abstract_inverted_index.A_{ac}	126
abstract_inverted_index.Edward	47
abstract_inverted_index.adding	112
abstract_inverted_index.easily	65
abstract_inverted_index.edges.	132
abstract_inverted_index.family	20
abstract_inverted_index.labels	4
abstract_inverted_index.matrix	86
abstract_inverted_index.powers	123
abstract_inverted_index.sorted	81
abstract_inverted_index.tested	19
abstract_inverted_index.traces	79, 119
abstract_inverted_index.vertex	3, 25, 50, 76, 93
abstract_inverted_index.$(a,b)$	130
abstract_inverted_index.Spence,	48
abstract_inverted_index.already	95
abstract_inverted_index.dataset	45
abstract_inverted_index.further	68
abstract_inverted_index.graphs,	14, 62
abstract_inverted_index.nonzero	128
abstract_inverted_index.problem	152
abstract_inverted_index.regular	13, 35
abstract_inverted_index.A_{bd}$,	127
abstract_inverted_index.Proposed	114
abstract_inverted_index.dataset,	109
abstract_inverted_index.graphs),	36
abstract_inverted_index.problem,	144
abstract_inverted_index.proposed	17, 49, 71, 75
abstract_inverted_index.standard	1
abstract_inverted_index.vertices	11
abstract_inverted_index.(strongly	34
abstract_inverted_index.adjacency	85
abstract_inverted_index.diagonals	82, 121
abstract_inverted_index.difficult	32, 139
abstract_inverted_index.vertices.	40
abstract_inverted_index.considered	136
abstract_inverted_index.invariants	51, 77, 116, 147
abstract_inverted_index.polynomial	23, 154
abstract_inverted_index.restricted	88
abstract_inverted_index.analogously	118
abstract_inverted_index.application	69
abstract_inverted_index.distinguish	9, 56
abstract_inverted_index.inexpensive	22
abstract_inverted_index.invariants,	28
abstract_inverted_index.invariants.	73
abstract_inverted_index.isomorphism	143
abstract_inverted_index.neighborhood	91
abstract_inverted_index.Specifically,	74
abstract_inverted_index.distinguished	66
abstract_inverted_index.$(A\|_{N_a})^p$	84
abstract_inverted_index.distinguishing	29, 98
abstract_inverted_index.Weisfeiler-Leman	2
abstract_inverted_index.$\bar{A}_{ab,cd}=A_{ab}	125
abstract_inverted_index.algebraic-combinatorial	146
cited_by_percentile_year
corresponding_author_ids	https://openalex.org/A5109420627
countries_distinct_count	0
institutions_distinct_count	1
citation_normalized_percentile