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
1answer
106 views

Finding sphere-like topologies in a nonplanar granular graph (help with problem definition)

Update/clarification: I'm looking for an elegant problem definition, not necessarily a solution, so please feel free to answer in that vein. (also check the end for additional clarifications) NOTE: I ...
1
vote
1answer
125 views

Gradient of a function on the vertices of a graph

Let $G=(V,E)$ be a graph. The gradient of a function $f:V\longrightarrow R$ is defined on the edges of the graph, given by the discrete derivative $$ \nabla f(e)=f(y)-f(x), \quad e=(x,y) \in E $$ ...
0
votes
1answer
243 views

difference between graph and multigraph

Question: Does there exist a multigraph G of order 8 such that Minimum d(G) = 0 while Maximum d(G) = 7? What if ‘multigraph G’ is replaced by ‘graph G’? Answer: such multigraph does not exist, but ...
2
votes
2answers
1k views

A connected k-regular bipartite graph is 2-connected.

I've been struggling with this exercise; all ideas have been unfruitful, leading to dead ends. It is from Balakrishnan's A Textbook of Graph Theory, in the connectivity chapter: Prove that a ...
3
votes
1answer
115 views

Another question in Graph Theory

Question: Let $H$ be a graph of order 10 such that $3\le d(v)\le5$ for each vertex $v$ in $H$ [where $d(v)$ is the degree of $v$]. Not every vertex is of even degree. No two odd-degree vertices are of ...
1
vote
3answers
632 views

Question of Graph Theory

Question is: Let G be a graph of order 8 and size 15 in which each vertex is of degree 3 or 5. How many vertices of degree 5 does G have? Construct one such graph G. Answer: I think this cannot be ...
1
vote
1answer
112 views

What is the average distance of a combination set?

I'm working on a genetic algorithm and would like to map each function to a set of "codons". So + -> 011. Given this, I would like to figure out how easy it would be for any given codon set to mutate ...
2
votes
0answers
119 views

Categorizing graphs disconnected by removing any two edges

I was thinking about 2-edge connected graphs, connected graphs that cannot be disconnected without removing at least two edges. I was thinking about a slight variant on this problem - what sorts of ...
2
votes
1answer
48 views

What is the maximum possible number of k-length geodesics in an n-vertex connected graph?

Suppose we have an $n$-vertex connected graph, $G$. For any given $i, j \in V(G)$, what is the maximum possible number of $k$-length geodesics that can exist between $i$ and $j$, where $1 \lt k \leq ...
3
votes
2answers
235 views

How to show the complete graph $K_5$ has no abstract dual

How do you show that the dual of the matroid obtained from the 5-vertex complete graph $K_5$ is not graphic, or equivalently, that $K_5$ has no abstract dual? I assume graphs considered here are ...
1
vote
2answers
289 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
60 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
87 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
271 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
52 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
230 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
817 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} & ...
14
votes
3answers
4k 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
384 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
480 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 ...
12
votes
0answers
379 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
490 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
89 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
241 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
438 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
387 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
82 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
622 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
705 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
533 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
92 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
149 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
202 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
99 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
126 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
264 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
603 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
164 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
666 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
2answers
437 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
113 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
91 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
88 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- ...
3
votes
1answer
684 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
1answer
318 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
122 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
73 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
118 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 ...