3
votes
1answer
82 views

What are the big issues in modern graph theory?

This is inspired by the similar question on modern set theory. I've read through the open problems in graph theory on Wikipedia's list of unsolved problems in mathematics, but what I'm looking for is ...
13
votes
3answers
3k views

The Best Strategy and Highest Possible Score for the “Threes!” Game.

[There's still the strategy to go. A suitably robust argument that establishes what is statistically the best strategy will be accepted.] Here's my description of the game: There's a $4\times 4$ ...
0
votes
0answers
38 views

Standardizing the terminology of graph theory

I took a course in graph theory many years ago and remember being frustrated that the terminology was not at all standardized (or didn't seem to be). Various sources used vastly different words or ...
1
vote
4answers
261 views

The fundamental group of Cayley graph

Today I read a math book and find interested in Theorem. Every group has its graph representation. And we call it cayley graph. Now we sort out the question Firstly, if we have a group, ...
17
votes
3answers
292 views

Results in graph theory proved using other areas of math, and vice versa

I'm curious about learning graph theory, as it seems to pop up in some unexpected places. In order to get a partial feel for the subject, I was wondering if anyone could point me to some survey ...
2
votes
1answer
127 views

Software for generating Cayley graphs of $\mathbb Z_n$?

Does it exist any program (for linux) which can generate a nice Cayley graph of any $\mathbb Z_n$? (If it's possible to create such a graph at all, that is.) (where perhaps $n ≤ 100$ or something ...
6
votes
3answers
173 views

How much topology for graph theory?

I am writing a thesis in the context of descriptive complexity in theoretical computer science and therefore need to study a little bit of graph theory. My background is not mathematics but computer ...
2
votes
0answers
107 views

Lattice theory in mathematics and physics

I have undertaken a project examining lattice model and trying to construct algorithm that could work on all lattice (in physical sense, or crystal structure). I notice there is a branch in ...
3
votes
2answers
227 views

Isn't seven bridges problem trivial? [closed]

What was the actual actual problem that led Euler to graph theory? By looking even at non-simplified map like this It is obvious that, if a landmass is connected by odd number of bridges, it ...
19
votes
3answers
698 views

Why should “graph theory be part of the education of every student of mathematics”?

Until recently, I thought that graph theory is a topic which is well-suited for math olympiads, but which is a very small field of current mathematical research with not so many connections to ...
2
votes
3answers
131 views

Drawing graphs (vertices and edges) with or without technology

Given a collection of vertices $V$ and a collection of edges $E \subseteq V\times V$, is there an algorithm or program that will allow you to draw a nice graph? The placing of the vertices is very ...
1
vote
0answers
44 views

What's the interested topic or applications about random graph, probabilistic method or combination?

I want to pick some topics or applications to do a project of a current course. Those topics should be related to graph theory, combinatorics, random graph, probabilistic method etc. Such as social ...
8
votes
3answers
476 views

What are some measures of connectedness in graphs?

I am not a mathematician (I am an engineer who is working on improving his mathematics), so I apologize in advance if my question is trivial. Consider a graph of $N$ nodes, with some defined ...
4
votes
5answers
834 views

Graph Theory Applications?

What are the areas where graph theory can be applied? Cause I wonder what applications this have on the real world. Does it solve certain problems and stuff? Areas such as communication networks ...
0
votes
1answer
357 views

What is the definition of a network in graph theory

From Wikipedia a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot ...
1
vote
1answer
214 views

Reference: Compendium of interesting graphs

I've been writing a little about some results on graph theory, and I want some nice examples of applying the results to some interesting finite connected graphs to show how the results might be ...
7
votes
3answers
1k views

Significance of eigenvalue

When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me?
2
votes
2answers
147 views

Organising a Tournament

Imagine the following Problem. The Student Union wants to organise a tournament with 2k participants ( $k \in \mathbb{N}$ ). There are to be m rounds and in each round players should be paired ...
2
votes
1answer
115 views

Eccentricity of a vertex

Eccentricity of a vertex $v$ in a graph $G$ is defined as max $\{d(v,w):w\in V(G), w\ne v\}$. My question is why is the word eccentricity used, what is the reason? Thanks
2
votes
0answers
161 views

Dimensions of Homology Groups

What does a dimension of a homology group tell us? In particular, suppose we form an arbitrary simplicial complex $S(G)$ from a simple graph $G$. Then we compute the homology groups of $S(G)$ and note ...
12
votes
3answers
2k views

Homology and Graph Theory

What is the relationship between homology and graph theory? Can we form simplicial complexes from a graph $G$ and compute their homology groups? Are there any practical results in looking at the ...
2
votes
0answers
70 views

Comparing symbolic and analog descriptions

I've never seen the following comparison before. Let me start with a specific example: Given a finite structure with two symmetric binary relations, i.e. a graph $G$ with one vertex set $V$ and two ...