Graph details

Graph # 34017

Adjacency matrix

00000000000001
00000000000001
00000000100000
00000000000010
00000000001000
00000000001000
00000000000100
00000000010000
00100000000100
00000001000011
00001100000001
00000010100010
00010000010100
11000000011000

Adjacency list

1: 14
2: 14
3: 9
4: 13
5: 11
6: 11
7: 12
8: 10
9: 3 12
10: 8 13 14
11: 5 6 14
12: 7 9 13
13: 4 10 12
14: 1 2 10 11

HoG graph id

34017

Graph name

Udelta Adjacency Graph

Graph submitted by

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic Yes Index 2.37
Algebraic Connectivity 0.104 Laplacian Largest Eigenvalue 5.508
Average Degree 1.857 Longest Induced Cycle undefined
Bipartite Yes Longest Induced Path 7
Chromatic Index 4 Matching Number 6
Chromatic Number 2 Maximum Degree 4
Circumference undefined Minimum Degree 1
Claw-Free No Minimum Dominating Set 6
Clique Number 2 Number of Components 1
Connected Yes Number of Edges 13
Density 0.143 Number of Triangles 0
Diameter 7 Number of Vertices 14
Edge Connectivity 1 Planar Yes
Eulerian No Radius 4
Genus 0 Regular No
Girth undefined Second Largest Eigenvalue 1.956
Hamiltonian No Smallest Eigenvalue -2.37
Independence Number 8 Vertex Connectivity 1

A table row rendered like this indicates that the graph is marked as being interesting for that invariant.

Comments

Posted by Kevin Ryde at Sep 28, 2019 8:36 AM.
Baker, McNulty, and Taylor, give a word Udelta = "ab w bc x ca y ba z ac", which is 4-avoidable but not 3-avoidable, and define a bipartite adjacency graph AG(Udelta) of the word.

Each vertex is a letter a,b,c,d,w,x,y,z from the word plus a side right R or left L. Each edge is where two letters of Udelta are adjacent on their respective sides. So "ab" in the word is an edge from vertex aR to vertex bL, indicating that the right side of a is adjacent to the left side of b. Then bR to wL, and so on. The result is a tree. aR is the degree-4. w,x,y,z are the 8 degree-1s since they occur only once each in Udelta.

Kirby A. Baker, George F. McNulty, Walter Taylor, "Growth Problems for Avoidable Words", Theoretical Computer Science, volume 69, number 3, 1989, pages 319-345. The present graph is their section 7 figure 2.

You need to be logged in to be able to add comments.