Graph details

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

ClawFree

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 4avoidable but not 3avoidable, 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 degree4. w,x,y,z are the 8 degree1s 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 319345. The present graph is their section 7 figure 2.
You need to be logged in to be able to add comments.