Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
2answers
340 views

What's the equivalent of the adjacency relation for a directed graph?

I've found several sources describing a relation notated $\sim$ signifying adjacency in an undirected graph, but nothing explicitly describing an equivalent for a directed graph. I've been using ...
0
votes
0answers
64 views

Approximating number of nodes expanded by A* search

When searching over a graph expressed as a uniform, 8-connected grid using the A* algorithm, is there any way to give a rough approximate of the number nodes expanded? I appreciate this is a somewhat ...
1
vote
0answers
89 views

Tricky computations in graph theory proof

Let $0 < p < 1$ be a constant, and set $b = 1/p$. Let $0 < \epsilon < 1/2$. Given a natural number $r \ge 2$, let $n_r$ be the maximal natural number for which $\binom{n_r}{r} ...
3
votes
4answers
285 views

Graph Theory: what are the two vertices and how to draw them?

Define a graph $G$ such that $V(G) = \{2,3,4,5,11,12,13,14\}$ and two vertices $s$ and $t$ are adjacent if and only if $\gcd\{s,t\} = 1$. Draw a diagram of $G$ and find its size $e(G)$. I can ...
1
vote
0answers
59 views

Bridge in a multigraph

According to Wikipedia, "a bridge in an undirected graph is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in ...
3
votes
4answers
265 views

Computing a sum of binomial coefficients

Does anyone know a better expression than the current one for this sum? $$ \sum_{i=0}^m \binom{N-i}{m-i}, \quad 0 \le m \le N. $$ It would help me compute a lot of things and make equations a lot ...
1
vote
1answer
1k views

How to prove that a matrix is positive definite?

Let $L$ be a Laplacian matrix of a strong connected and balanced directed graph. Define $$ L^{s}=\frac{1}{2}\left( L+L^{T}\right) .$$ Let $D$ be a diagonal matrix with $$ D=\begin{bmatrix} d_{1} & ...
15
votes
3answers
3k views

Average Scrabble graph structure: diameter?

Tonight a game of Scrabble ended in what I consider a very unusual graph structure, unlike this generic web image, which seems more typical: ...
2
votes
1answer
447 views

What's behind Conway's Game of Life search algorithms?

I've been looking at a program gfind, that searches for spaceships in Conway's Game of Life. The documentation says a bunch of stuff about searching De-Bruijin graphs. I couldn't find any useful ...
0
votes
2answers
593 views

Why is every irreducible matrix with period 1 primitive?

In a certain text on Perron-Frobenius theory, it is postulated that every irreducible nonnegative matrix with period $1$ is primitive and this proposition is said to be obvious. However, when I tried ...
13
votes
0answers
449 views

Normalizers of automorphism groups

In abstract groups $\Gamma$ the normalizer $N_\Gamma(S)$ of a subset $S\subseteq\Gamma$ is the subgroup of all $x \in \Gamma$ that commute with $S$, i.e. $xS = Sx$, i.e. $x\ y\ x^{-1} \in S $ for all ...
0
votes
1answer
671 views

Affine plane of order 4?

I cannot seem to construct an affine plane of order 4. I have the construction for order 3- but cannot seem to come up with or find the construction for 4 anywhere. Could someone show me a picture of ...
4
votes
1answer
99 views

Name for a type of subgraph that comes from identification of vertices?

Is there a special name for the kind of subgraphs you get by taking some sequence of the following operation: Pick two vertices and identify them so all edges going to either vertex get sent to the ...
4
votes
1answer
314 views

Is every forest with more than one node a bipartite graph?

This is a question from my exam today: The definition of a bipartite graph is: "A graph with at least two nodes is bipartite if and only if there is no odd-length cycle in the graph." We'll ...
8
votes
1answer
488 views

Szemerédi's Regularity Lemma

I am trying to understand the statement of the Szemerédi's Regularity Lemma as explained here, but am not able to wrap my head around to what it really means. In particular the concept of ...
1
vote
1answer
447 views

Counting the number of graphs on n vertices

I want to count the number of simple graphs on $n$ vertices where it is given that there is a fixed $K_k$ among those $n$ vertices. The way I am reasoning is this: the edges within the $n-k$ non-$K_k$ ...
2
votes
1answer
84 views

simple algebraic problem (related to graph theory)

Given $\binom{n}{r} p^{\binom{r}{2}} = 1$, I want to obtain an expression for $r$. In particular, applying Stirling approximation $$n! \sim \sqrt{2 \pi n} (n/e)^n$$ We see that $$\binom{n}{r} ...
1
vote
1answer
807 views

Calculating distance in a hexagonal grid map

Say I have this map: The first two digits on each hex represent the X axis, the last two digits the Y axis, with 60º between both. How do I calculate the shortest distance between two hexes? E.g. ...
3
votes
2answers
1k views

Graph theory exercise on finding a subgraph with minimum degree.

I was doing some practice problems in graph theory and would appreciate some help on this one. This problem is from a practice exam from the discrete mathematics course at Princeton. Consider a graph ...
0
votes
1answer
626 views

Find the maximum number of vertex-disjoint paths in a graph with a constraint

Given a undirected graph G=(V,E), each edge is associated with a non-negative value. How to find the maximum number of vertex-disjoint paths from s to t on the graph G, with a constraint that the ...
2
votes
1answer
79 views

2012-gon- subsets of vertices.

Can we prove or disprove this? For a sufficiently large $n$, every set of at least $ n$ points in the plane with no three collinear has a subset that form the vertices of a convex $2012$-gon. Gerry ...
0
votes
2answers
103 views

Complete graph-coloring

Can we prove or disprove the following statement? For any graph $H$ and any coloring $c$ of its edges with two colors, there exists $n$ such that every $2$-coloring of the edges of the complete graph ...
1
vote
2answers
224 views

Partial latin square with $\le n-1$ filled cells

How do we show that is $P$ if a $n\times n$ Latin square with $\le n-1$ filled cells, then $P$ can be completed to a proper Latin square? Here is the definition of a Latin square. (WHAT I HAVE DONE ...
1
vote
1answer
220 views

Number of connected subgraphs of the complete unlabelled graph

Is there an explicit formula for the number of connected graphs with at most $n$ vertices?
1
vote
1answer
108 views

Graph theory question involving probabilistic method.

I was trying to prove the following statement using probabilistic methods: Given that $G$ is a graph on $n\geq 10$ vertices, is a graph that has the property: If we draw a new edge, then the number of ...
2
votes
1answer
133 views

number of distinct hamiltonian-path graphs that have equal number of vertexes and share degree

There definitely are traceable graphs (hamiltonian-path graph) that have equal number of vertexes and have equal degree information - for example, graph A has vertex A that has degree of three, vertex ...
0
votes
1answer
294 views

Loopless graph-proof

Let $G$ be a loopless graph with no isolated vertices. Let $X$ be a largest matching in $G$ and let $Y$ be a smallest set of edges of $G$ so that every vertex of $G$ is incident with at least 1 edges ...
0
votes
1answer
735 views

k-edge-connected graph- proof

Call a graph k-edge connected iff for every set $X$ of fewer than $k$ edges, $G|X$ is connected. Prove that every 2-edge connected graph has a perfect matching. I would go about this starting with ...
1
vote
1answer
188 views

perfect matching-proof

Let every vertex of a graph $G$ have $\delta=3$ and let $G$ have no cut-edge. Then prove that $G$ has a perfect matching. A cut edge is an edge whose deletion increases the number of connected ...
0
votes
3answers
930 views

bipartite simple graph matching-proof

Prove that if $G$ is a bipartite simple graph and every vertex has the same degree $k$, then the edges of $G$ can be partitioned into $k$ matchings. Can we then prove the same if every vertex has ...
1
vote
3answers
575 views

Measure the connection between two nodes in a graph

This is a question about complex networks We have various ways to measure the centrality or importance of a node. $$\textrm{importance} :: \textrm{node} \rightarrow \mathbb{R}$$ The simplest such ...
0
votes
1answer
122 views

Critical graph inequality - proof?

I am curious to see a rigorous proof of the following inequality; if $G$ is a $k$-critical graph, then $$k(|V(G)|-1)\le2|E(G)|.$$ Does anyone know if it is a well known inequality? If so what ...
0
votes
0answers
23 views

k-critical graph inequality- edges and vertices [duplicate]

Possible Duplicate: critical graph inequality- proof? I am curious to see a rigorous proof of the following:If $G$ is a $k$-critical graph, then $k(|V(G)|-1)\le2|E(G)|$. Does anyone know if ...
0
votes
1answer
99 views

Unit distance graph in $\mathbb{R}^2$

Suppose $G$ is the simple graph with vertex set $\mathbb{R}^2$ created by connecting two points iff they are distance one from each other in the plane. How can we prove that $4\le \chi(G)\le7$? I ...
0
votes
2answers
93 views

r-colorable simple graph

What $r$ colorable simple graph on $n$ vertices has the most edges? Is there a unique such graph? I am told this has something to do with Turan's theorem... (This is the progress I have made- ...
4
votes
1answer
970 views

edges and chromatic number inequality

I have not been able to find a proof to the statement that if a graph $G$ has $\chi(g)=k$, then it must have at least $\binom{k}{2}$ edges. Would you be able to show me a simple proof?
1
vote
2answers
492 views

Clique number and chromatic number equal for interval graph-proof

I cannot seem to find a proof anywhere for the following lemma: Show that for any interval graph, the chromatic number is equal to the clique number. The lemma is used everywhere but I cannot find a ...
1
vote
0answers
134 views

General theory of graph coloring

In Ben Steven's article Colored graphs and their properties I read: We "color" a graph by assigning various colors to the vertices of that graph. [...] this process of coloring is generally ...
-1
votes
2answers
75 views

Work out the number of edges given conditions of a graph

Given a set of nodes $V$, and a parameter $c \lt |V|$, How can we show that whether we can derive an un-directed graph $G=(V,E)$ where the degree of each node equals to $c$? If a graph as above ...
2
votes
1answer
119 views

Counting the number of back-tracking closed walks on a 2D grid.

Given a reference node at an infinitely spanning 2D grid, how can I express the number of back-tracking closed walks (closed walks that does not contain cycles) for that node in terms of L, which is ...
1
vote
1answer
154 views

Vertex Cover - upper bound

A few definitions: $\mathsf{VC} = \{ (G,k) \mid \text{There exists a vertex cover of size $k$ in $G$}\}$ $\mathsf{VC_{LOG}} = \{ G \mid \text{There exists a vertex cover of size $\leq \log |V|$ in ...
6
votes
1answer
1k views

Edge-coloring of bipartite graphs

A theorem of König says that Any bipartite graph $G$ has an edge-coloring with $\Delta(G)$ (maximal degree) colors. This document proves it on page 4 by: Proving the theorem for regular ...
0
votes
1answer
185 views

How do you prove that a game is undecidable?

I'm studying a game that is played on a graph, there are two teams, attackers and defenders. The attackers are attempting to capture the King by occupying all of his neighbours, the defenders are ...
0
votes
1answer
452 views

All Bipartite Graphs on n number of vertices

I need to find a list of all connected bipartite graphs on 15 vertices. http://mapleta.maths.uwa.edu.au/~gordon/remote/graphs/index.html#bips lists all graphs on 14 or fewer number of vertices. ...
1
vote
1answer
428 views

Approximation ratio for the b-Matching problem

For an undirected graph $G=(V,E)$ and a bound on the vertex degree $b: V \rightarrow \mathbb{N}$, I am looking into the problem of finding a maximal subset $H$ of $E$, such that each vertex $v\in V$ ...
4
votes
1answer
149 views

“Isolated” pieces in figures of triangles

Let us consider a figure of the Euclidean plane comprised of finitely many non-degenerate non-overlapping triangles (i.e., no triangle has a zero area and no two distinct triangles have any inner ...
0
votes
1answer
345 views

Name for a graph with two types of vertices $U, V$, where the end points of edges are either both in $U$, or one is in $U$ and the other in $V$?

I know that a graph whose vertices can be divided into two sets $U$ and $V$ such that every edge can only connect a vertex in $U$ to one in $V$ is called a bipartite graph. Is there a name for a type ...
7
votes
2answers
787 views

Degeneracy of outerplanar graphs

Does anyone know an elegant proof to the fact that every outerplanar graph has a vertex of degree at most 2 (and hence is 2-degenerate, since every subgraph is also outerplanar). I have a proof by ...
3
votes
1answer
60 views

Convex programming when the problem has an underlying combinatorial structure that's a DAG

I have a nonlinear convex objective function to minimize. The function is defined on a set of variables: $\{ x_1,x_2, \ldots ,x_p \},$ where each $x_i$ is a number associated with a path in the DAG. ...
3
votes
1answer
162 views

When are all closeness centralities zero?

I have a theoretical question, but it is not homework. The closeness centrality values of all vertices are 0 if the graph is disconnected. Are there other cases where the closeness centrality ...