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

36
votes
2answers
608 views

Counting trails in a triangular grid

A triangular grid has $N$ vertices, labeled from 1 to $N$. Two vertices $i$ and $j$ are adjacent if and only if $|i-j|=1$ or $|i-j|=2$. See the figure below for the case $N = 7$. How many trails ...
2
votes
0answers
561 views

Dynamic programming problem and shortest path problem

I was wondering if any dynamic programming problem can always be converted to a source-sink shortest path problem in a network with source and sink nodes given? And vice versa? Is any dynamic ...
3
votes
4answers
346 views

Examples of theorems in graph theory

I'm looking for examples of uses of the incidence matrix in graphs for my class (apart from proving that for a graph $G=(V,E)$ we have $2|E|=\underset{v\in V}{\sum}d(v)$). Can you think of anything ...
0
votes
0answers
201 views

Strongly-Connected Components's Graph by running DFS

I got this question, and I'd be happy for help. G=(V,E). $G_S$ is a Strongly-Connected Components's Graph. I need to prove, that if there is only one Component ($C_0$) which is not with incoming ...
2
votes
1answer
155 views

How do I model poker hands as graphs such that I can evaluate using graph isomorphism?

These two poker hands are graph isomorphic via a trivial suit-shifting function f: G = Ah Kc Qd Js Th H = Ac Kd Qs Jh Tc V(H) = f(V(G)) where f shifts the suits Question: how do I ...
1
vote
2answers
308 views

Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)

I got this question, and I'd be happy for help. There is a graph G=(V,E), directed graph, and F is subset of E. I need an algorithm which find if there is a cycle composed from one (or more) of the ...
2
votes
3answers
158 views

Functions, graphs, and adjacency matrices

One naively thinks of (continuous) functions as of graphs1 (lines drawn in a 2-dimensional coordinate space). One often thinks of (countable) graphs2 (vertices connected by edges) as represented by ...
3
votes
3answers
472 views

Isolated vertex probabilities for different random graphs

I'm trying to teach myself a little more on threshold probabilities for random graphs, and I'm looking at the probability that graphs have an isolated vertex, when we add on a few restrictions (when ...
2
votes
1answer
554 views

Problem about number of vertices of a graph

Here is a sample problem I need to know how to solve: The complementary graph $\overline{G}$ of a simple graph $G$ has the same vertices as $G$. Two vertices are adjacent in $\overline{G}$ if and ...
4
votes
1answer
226 views

What is the maximum length of shortest odd cycle in a non-bipartite graph?

Let $G = (V, E)$ be a connected, undirected, and non-bipartite graph. What is the maximum length of the shortest odd cycle? I'm working on an algorithm for computing bipartivity degree. See, for ...
1
vote
2answers
1k views

How many non-isomorphic graphs with $5$ vertices and $3$ edges are there?

how many non-isomorphic graphs are there with 5 vertices and 3 edges?
1
vote
0answers
148 views

l1-metric and cut metric equivalence

I would like to show that the following two statements are equivalent. Let (A, d) be an n-point metric space. And B set of $\binom{n}{2}$ pairs of points of A. $\exists t \geq 1$, integer m, and ...
6
votes
1answer
183 views

A graph $G$ is connected iff the coefficient of $x$ in $P(G,x)$ is nonzero?

I was talking to my brother today, and we came up with a little conjecture. Is it true that a graph $G$ of order $n$ is connected if and only if the coefficient of $x$ in the chromatic polynomial ...
4
votes
1answer
136 views

Necessary and Sufficient Conditions for Simplicity and Connectedness in Graphs

A connected graph is a graph with no disjoint subgraphs. A simple graph is a graph with no loops or multiple edges. Easy Question: What are the necessary and sufficient conditions on the order ...
10
votes
2answers
186 views

Embedding the Infinite Binary Tree in Regular Tilings

Consider the regular tiling $(m,n)$ in which $m$ $n$-agons meet at each vertex. Most of the time this tilings have to "live" in the hyperbolic plane. The edges of its polygons define a graph where two ...
5
votes
2answers
533 views

Pairs of points exactly $1$ unit apart in the plane

This is a problem I found in a graph theory text, but I can't figure it out. Let $S$ be a set of $n$ points in a plane, the distance between any two of which is at least one. Show that there are at ...
1
vote
2answers
87 views

On one graphical sequence implying another sequence is graphical

I read this statement related to Havel and Hakimi. Suppose that $\textbf{d}=(d_1,d_2,\ldots,d_n)$ be a nonincreasing sequence of nonnegative integers. Let $\textbf{d'}=(d_2-1,d_3-1,\ldots, ...
2
votes
1answer
166 views

Kinks in the eigenvalue spectrum of short range lattices

Take a periodic one-dimensional lattice of size $N$ with $2k$ nearest neighborers. That is, vertex $i$ is connected to $i+1,i+2,...,i+k$ and $i-1,i-2,...i-k$ (with the understanding that the indices ...
2
votes
2answers
169 views

How to count the no. of distinct ways in which 1,2,…,6 can be assigned to 6 faces of a cube?

How to find the number of ways in which six digits 1,2,..,6 can be assigned to six faces of a cube (without repetition of digits) so that one arrangement cannot be obtained from another by a rotation ...
6
votes
1answer
312 views

For a graph $G$, if $m>\binom{n-1}{2}$, then $G$ is connected

I'm trying to pick up a little graph theory out of Bondy and Murty's Graph Theory as suggested here. Problem 1.1.12 has given me a little hitch. Let $G$ be a simple graph of order $n$ and size ...
5
votes
1answer
804 views

Simplification of the Erdos-Gallai Theorem

A week or two ago back I was pointed to the Erdos-Gallai Theorem in this question. I've been unable to locate a satisfactory proof of this theorem, since the reference on wikipedia is in Hungarian. ...
1
vote
2answers
2k views

problem to determine the chromatic polynomial of a graph

for a homework graph theory, I'm asked to determine the chromatic polynomial of the following graph this is my thread in another post: ...
4
votes
1answer
100 views

Does the Robertson-Seymour theorem apply to vertex-labeled graphs?

Does the Robertson-Seymour theorem apply to vertex-labeled graphs? A minor as I understand it is a graph which can be reached by a sequence of edge contractions and non-disconnecting edge deletions. ...
4
votes
1answer
143 views

Discovering properties of a graph by means of random walk

Suppose I have a regular, undirected, non-bipartite, finite, connected graph on $N$ vertices. Some fraction $\frac{c}{N}$ of the vertices are coloured gold, the rest are coloured black. If I let you ...
1
vote
1answer
239 views

eigen decomposition of an interesting matrix (general case)

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{ 0, 1, .., b-1 ...
3
votes
1answer
330 views

Construct dual network for conversion of min-cut problem to shortest path problem

I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. ...
5
votes
3answers
885 views

Does there exist a general graph for any degree sequence of even natural numbers?

Suppose you have a given degree sequence $(d_1,d_2,\dots,d_n)$, where $d_i$ is even for every $i$. Does there exist a general graph with this degree sequence? I say yes, the easiest way is to take ...
3
votes
1answer
387 views

Number of isomorphic graphs for a particular digraph

Suppose we have a simple digraph $G$ with $g$ vertices and $a$ arcs. How should one count all graphs in that isomorphism class (i.e., all graphs isomorphic to graph $G$). Any pointers would be really ...
4
votes
1answer
56 views

Number of realizations of particular triad type

Given four types of triads (figure below) their probabilities in a random Bernoulli digraph are as follows: $T_{003}$: $(1-p)^6$ $T_{012}$: $6p(1-p)^5$ $T_{102}$: $3p^2(1-p)^4$ $T_{111D}$: ...
7
votes
3answers
128 views

graphs on surfaces

I'm looking for references on embedding graphs in surfaces (motivation: I was doodling and wondered how many distinct embeddings of $K_{3,3}$ into the torus there are.)
4
votes
1answer
332 views

eigen decomposition of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
2
votes
2answers
781 views

Uses of Strongly Connected Components?

I recently learned about SCCs in directed graphs and how to find them, yet I have no clue what they are useful for. If you collapse each SCC into a node, you get a new graph that has no cycles. But ...
3
votes
1answer
258 views

Getting edge cut from eigenvector of adjacency matrix

Given a $d$-regular undirected graph and an eigenvector of its adjacency matrix, how can I get an edge cut from it? My idea was to do something similar as in the proof of the Cheeger inequality, but ...
4
votes
0answers
291 views

Bellman-Ford algorithm with changes

I got this question and I will be happy for a clue. Here is a similar algorithm to the Bellman-Ford algorithm: ...
1
vote
1answer
331 views

Current exciting topics in graph theory

What is new in the world of graph theory in the past few years? Beyond the basics?
4
votes
0answers
109 views

Are almost all rooted trees asymmetric?

It's well known that almost all graphs are asymmetric (have trivial automorphism group) and that almost all free trees are symmetric. By which argument do I see whether almost all rooted trees are ...
5
votes
1answer
342 views

Rank of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
7
votes
7answers
1k views

What software is used to draw undirected graphs?

I need to make a nicer-looking version of this image: Is there some program that generates these graphs? Or are they done by hand in something like Visio? (I'm on Mac OS X, and I have access to ...
1
vote
2answers
704 views

What is a 2-regular graph?

What is a 2-regular graph? Is is the same thing as an 2-connected graph where a 2-connected graph is a graph G such that G-V ( G minus a vertex V) is still connected?
3
votes
1answer
113 views

Given a graph $G$, how to find all disjoint edges?

I have an undirected graph $G$, with edges $E$ and vertex $V$, how to group the edges into different sets, in which One edge can only belong in one set Every edge must be covered in one of the sets ...
1
vote
1answer
78 views

Proving that a cycle basis has the properties of a matroid

I'm given an assignment to prove that a cycle basis has the properties of a matroid. But I'm having problems trying to understand the paragraph below excerpted from here Let a matroid be a set of ...
8
votes
2answers
4k views

Graph terminology: vertex, node, edge, arc

Precisely speaking, what is the difference between the graph terms of ("vertex" vs. "node") and ("edge" vs. "arc")? I have read that "node" and "arc" should be used when the graph is strictly a tree. ...
2
votes
4answers
4k views

Is a graph simple, given the number of vertices and the degree sequence?

Does there exist a simple graph with five vertices of the following degrees? (a) 3,3,3,3,2 I know that the answer is no, however I do not know how to explain this. (b) 1,2,3,4,3 No, as the sum of ...
3
votes
1answer
310 views

network flow as a linear combination

How would I write the flow of the following graph as a linear combination of flows along s,t-paths and t,s-paths and cycles? The values of the edges in the graph represent the flow along that edge. ...
4
votes
3answers
1k views

Proving that a graph of a certain size is Hamiltonian

For any graph with order $n \geq 3$, given that its size is $$m \geq \frac{\left(n-1\right)(n-2)}{2} + 2,$$ show that the graph is Hamiltonian. I know that if I can show that the degree sum of any ...
3
votes
1answer
168 views

How many different four coloring exist for a given regular map?

Excluding maps that can be colored with 2 or 3 colors, how many different four coloring exist for a given regular map? Naturally, two identical maps have to be regarded as differently colored if the ...
1
vote
1answer
272 views

How many directed graphs with N nodes contain a given directed cycle of length L?

Given a directed graph $C$ that only contains a directed cycle of length $L$ (and all resulting sub-cycles), that visits each node at least once, $$C=(V, D)$$ where $V$ is a fixed set of vertices ...
-1
votes
1answer
213 views

Uniform Cost Search on Graph Proof

I am trying to prove the following: For any positive natural n, there exists an undirected graph of n nodes, positive natural edge widths, and nodes s and t such that a uniform-cost search from s ...
5
votes
1answer
1k views

Dijkstra's algorithm using heap

My teacher gave me a pseudocode of Dijkstra's algorithm using binary heap including the following steps (x was just extracted from the heap): For each vertex y such that it is a node for it in a ...
3
votes
2answers
238 views

isomorphic graphs adjacency lists

Is there an algorithm which will allow me to find an isomorphism between two graphs if I have their adjacency lists?