13
votes
2answers
677 views

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

[There's still the strategy to go . . . ] Here's my description of the game: There's a $4\times 4$ grid with some random, numbered cards on. The numbers are either one, two, or multiples of three. ...
0
votes
0answers
34 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 ...
0
votes
4answers
135 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, ...
16
votes
2answers
261 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
75 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
141 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 ...
1
vote
0answers
90 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
200 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 ...
18
votes
3answers
552 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
118 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
43 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
305 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
556 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
270 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
189 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
141 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
111 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
149 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 ...
11
votes
3answers
1k 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 ...