graph theory glossary

Any errors are mine.

_________________________________________________________________

For a graph G or a vertex V, define:

chromatic number
Least number of colors required to color all the adjacent
vertices of G differently.

circuit
Path that begins and ends at the same vertex.

clique
A complete subgraph of G. Sometimes the largest such subgraph.

complete
Every pair of vertices in G is connected by exactly one edge.

connected
On G there exists a path containing all vertices.

crossing number
The minimum number of crossings with which G can be drawn.

degree (valence)
Number of branches at V.

diameter
The longest geodesic in G.

dominating set
A subgraph S of G such that remaining vertices in G are adjacent
to vertices in S.

domination number
The size of the smallest dominating set in the given graph.

eccentricity
The longest geodesic involving the given vertex.

genus
The minimum number of handles that must be added to a plane to
embed the given graph without any crossings.

geodesic
The shortest path between a pair of vertices.

loop
Circuit of length 1 (an edge that connects a vertex to itself).

planar
A graph whose edges intersect only at its vertices.

radius
The shortest geodesic in a graph.

tree
A simple, undirected, connected, acyclic graph.

Following Gene's age-old suggestion, I will now attempt to tell
if various graph terminology have any music-theoretical importance.

Here vertices are pitches, and edges are consonant dyads.

Note: This is based on a slightly updated version of the glossary,
compared to the last post.

>chromatic number
>The least number of colors required to color all the adjacent
>vertices of G differently.

As this goes up, I assume edge connectivity goes up. And edge
connectivity is generally Good.

>circuit
>A path that begins and ends at the same vertex.

On the lattice, circuits would constitute scales that are "covered"
by dyads. Temperament allows a scale to be covered by a single
type of dyad.

>circumference
>The length of the longest circuit in G.

As this goes down, I assume edge connectivity goes up.

>clique
>A complete subgraph of G. Sometimes the largest such subgraph.

Maximal cliques of the n-limit lattice are saturated n-limit
chords. In JI they are either otonalities, utonalities, or ASSs.

>clique number
>The number of vertices in the largest clique of G.

Tells you the number of dimensions you need to lattice a scale.

>complete
>G for which every pair of vertices is connected by exactly one
>edge.

If G is complete all its dyads are consonant, but it may not be
a saturated n-limit chord. Tonal music tends to depend on scales
with several disjoint cliques. Though by the 9-limit you pick
up an extra 3:2, and the 6:7:9 chord can invoke a new tonality.

>connectivity, edge
>The minimum number of edges that must be deleted from G to render
>it disconnected.

Considered beneficial.

>connectivity, vertex
>The minimum number of vertices that must be deleted from G to
>render it disconnected.

Also good, but since we're generally more interested in intervals
than pitches, edge connectivity seems more natural.

>crossing number
>The minimum number of crossings with which G can be drawn.

The higher the better.

>degree (valence)
>The number of branches at V.

We don't care so much about V.

>diameter
>The longest geodesic in G.

The lower the better. See Paul Hahn's site.

>dominating set
>A subgraph S of G such that remaining vertices in G are adjacent
>to vertices in S.

The existence of many dominating sets of similar cardinality seems
like a Good Thing for tonal music. Kinda like what I said earlier
about cliques, except that here we know we can modulate easily
between subgraphs.

>domination number
>The size of the smallest dominating set in G.

Not sure it matters.

>eccentricity
>The longest geodesic involving V.

We don't care so much about V.

>genus
>The minimum number of handles that must be added to a plane to
>embed G in it without any crossings.

Higher the better.

>loop
>A circuit of length 1 (an edge that connects a vertex to itself).

Only for octaves!

>planar
>G whose edges intersect only at vertices.

Only for triadic music in JI, we hope.

>radius
>The shortest geodesic in G.

Less important than diameter.

-Carl

--- In tuning-math@yahoogroups.com, Carl Lumma <ekin@l...> wrote:

> >crossing number
> >The minimum number of crossings with which G can be drawn.
>
> The higher the better.

This connects to the genus, by the way, which is how many holes you
need to poke in your donut in order to not have any crossings if you
draw the graph on the donut.