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

2
votes
1answer
106 views

Graph isomorphism and existence of nontrivial automorphisms

Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism: (1) Decision problem: ...
0
votes
1answer
46 views

How to know if $(8,7,7,6,5,5,4,3,3,2,1,1)$ is a Simple Graph w/o using Havel-Hakimi Algorithm

I've used the Havel-Hakimi Algorithm to show this sequence $(8,7,7,6,5,5,4,3,3,2,1,1)$ is simple, but is somewhat time consuming for a test. Is there a way to determine without using algorithms? Or ...
1
vote
1answer
43 views

Vertex coloring proof question

There is a graph $G$ such that if any pair of vertices is removed, then its chromatic number decrease by $2$. Show that $G$ is complete graph.
1
vote
0answers
28 views

Conservativeness on a graph

I'm trying to build a conservative vector field out of something smaller than $\mathbb{R}^2$ to understand how the "conservative" property of differences-of-scalar-fields leads to Green's theorem. (In ...
0
votes
2answers
408 views

traveling salesman with pairs of cities, without return and with given start and end cities

I am looking for the name of the following two problems, and an approach to solve them. Problem#1: given N nodes, find the shortest path starting at a given start node and ending at a given end node, ...
0
votes
3answers
78 views

Find a graph on a torus (tutorial)

Find the $K_{4,4}$ graph on a torus. So, that's my homework. I've even found it in one of my textbooks, but only the solution, not a how-to-do-it method. I would really appreciate a step-by-step ...
1
vote
0answers
84 views

How many London underground stations you can visit without passing through the same station twice?

If you can start anywhere and only travel on the lines shown in the official map (http://www.tfl.gov.uk/assets/downloads/standard-tube-map.pdf) (including overground, DLR, Emirates Air Line and ...
3
votes
3answers
145 views

Is there a method for systematically enumerating sets of collinear nodes in a graph?

This question arises directly from the discussion in this MSE question which I'd posted a few days back: Counting the number of polygons in a figure. In that question, I'm currently trying to find a ...
1
vote
2answers
110 views

Finding number of paths between vertices in a graph

According to my book, this is how it's done: What exactly does $A^r$ represent? Here is an example they did and I have no clue where all those 8s and 0s came from..
3
votes
4answers
245 views

Chromatic Polynomial of Ladder Graph

Hey guys I am trying to understand the formula for the chromatic polynomial of a ladder graph. $$k(k-1)(k^2-3k+3)^{n-1}$$ Can you guys help me understand how we get to this?
2
votes
1answer
74 views

Minimal time to ride all ski slopes

Suppose we want to know what the minimum time is to ride all ski slopes on a mountain. We know the time it takes to ride a slope, and we know the time it takes to take a ski lift to get from one ...
0
votes
1answer
29 views

Defining a graph as G=(V,E) — how to interpret the notation?

I am looking at the following problem: Define $V=\{0,1,2,3,4,5\}$. Define a graph $G=(V,E)$ by letting the edges be: $$ E =\{(a,b):a-b^2 \le 1 \lor b-a^2 \le 1\}$$ I understand that 'V' stands for ...
2
votes
1answer
77 views

Flow Graphs: Why do you need the symmetry property of a graph?

$$\begin{gather} f(u,v) \le c(u,v) \tag{Capacity constraint} \\ f(u,v) = -f(v,u) \tag{Symmetry} \\ \sum_{\large{v \in V, v \ne s,t}} f(u,v) = 0 \tag{Conservation of flow} \end{gather}$$ When you are ...
2
votes
2answers
151 views

Determining if two graphs are isomorphic

I'm supposed to determine if the above graphs are isomorphic. I thought there was because there was a bijection from the set of vertices of graph G to the set of vertices of graph H, and because ...
1
vote
0answers
15 views

Reweight a graph to give it a small max cut

Let $G = (V, E)$ be an undirected, unweighted graph. I wish to assign weights (possibly negative, not all zero) to the edges to minimize the value of: $$\frac{m}{\|w\|}$$ where $m$ is the value of ...
4
votes
1answer
49 views

Does every graph arise as the commutativity graph of some group?

By graph let us mean a set $G$ together with a relation $\bot$ that is reflexive and symmetric. Now every group gives rise to a commutativity graph by defining $x \,\bot\, y \iff xy=yx.$ Does every ...
0
votes
1answer
29 views

Formal name for a closed connected graph

I have to name an abstraction representing a mechanical truss diagram. It consists of a set of polygons that must overlap, viz. share an edge or a corner. In other words it must not only be a ...
0
votes
1answer
38 views

Minimum cut for a graph?

I'm studying for finals and can't figure out the minimum cut for this graph: I came up with the augmenting paths: ...
0
votes
0answers
39 views

number of graphs satisfying specific degrees and number of vertices.

Is there a way to determine the number of graphs (up to isomorphism) for a given $n$ and multi set $\{ d_1,d_2...d_n \}$ ? such that the graphs have $n$ vertices and $\{ d_1,d_2...d_n \}$ is the ...
2
votes
1answer
99 views

How many paths of length $4$ are there in $K_{3,7}$?

Let vertices of bipartite graph $ K_{3,7} $ be $\{A_1\; A_2\; A_3\}$ and $\{ B_1 \; B_2\; B_3 \; \dots B_7 \} $. Q1. Is $\{A_1\; B_1\; A_2 \; B_2\; A_1\}$ following considered as one of the ...
0
votes
1answer
38 views

If G is a tree and $p_1,\ldots,p_n,q_1,\ldots,q_{n+1} $are points of it,how to prove the identity?

$\sum_{1\leq i<j\leq n}d(p_i,p_j)+\sum_{1\leq i<j\leq n+1}d(q_i,q_j)\leq\sum_{i=1}^n\sum_{j=1}^{n+1}d(p_i,q_j)$
2
votes
0answers
156 views

Counting the number of $(d_v,d_c)$ regular bipartite graphs

I am trying to count the number of $(d_v,d_c)$ regular bipartite graphs. To be specific, let $n,m,d_v,d_c$ be positive integers such that $$n\times d_v=m\times d_c.$$ Then, what is the number of ...
16
votes
3answers
1k views

Why there are $11$ non-isomorphic graphs of order $4$?

I'm new to graph theory and I don't plan to become a serious student of graph theory either. My book suggests that there are $11$ non-isomorphic graphs of order $4$, but I can't see why. I know that ...
1
vote
2answers
125 views

N-dimensional Hypercubes coloring

How many ways 3-cube vertices can be coloring using 10 color, vertices which have relation is not able to have same color. I would also appreciate anyone who show the solution for finding total ways ...
1
vote
0answers
58 views

Improved approximation algorithm for maximum weighted matching

I've read the discussion here: http://stackoverflow.com/questions/5203894/a-good-approximation-algorithm-for-the-maximum-weight-perfect-match-in-non-bipar, and I have implemented the Drake and ...
3
votes
1answer
40 views

Graph of polytope and hyperplane

Suppose that $P$ is a compact and convex polytope in $R^d$ and let $G$ be the graph of $P$ ($V(G)$ are the vertices of $P$ and $E(G)$ are the $1$-dimensional faces - for example polyedral graphs are ...
3
votes
1answer
86 views

Chromatic index of a graph with vertices of degree 3 and one of degree 2

I would like to prove that the chromatic index of a graph with vertices of degree 3 and one vertex of degree 2 is 4. I know: That this graph is in fact 3-regular graph (cubic graph) with one edge ...
0
votes
1answer
72 views

Counting acyclic tournaments

So, a question on my homework asks us to count the number of acyclic tournaments on $n$ vertices. I understand what it's asking, but I don't know how to even get started. This is a combinatorics class ...
0
votes
2answers
76 views

Minnor differences in notation used in definition of graphs

One of book states A graph G consists of two finite sets: a nonempty set V(G) of vertices and a set E(G) of edges, where each edge is associated with a set consisting of either one or two ...
0
votes
1answer
68 views

How can we compute the genus of the graph?

$V(G)=\{u_1,\cdots,u_7,v_1,\cdots,v_9, w_1,\cdots,w_5\}.$ Set $$E_1=\{u_1u_j |2\leq j\leq 7\}\cup\{u_1v_j |j=1,3,5,6,8,9\}\cup\{u_1w_3,u_1w_4\};$$ $$E_2=\{u_2u_j | j= 3, 4,6,7\}\cup\{u_2v_j ...
2
votes
1answer
51 views

Why must the subgraphs that make up the solutions to Instant Insanity be disjoint?

I keep hearing that the subgraphs to the game Instant Insanity must be disjoint. Why is this true? What if the same two colour on the front and back of a cube are the same two colours on the sides of ...
4
votes
1answer
132 views

Sufficient condition for graph to have triangle

I need a sufficient condition for graph to have triangle (exists $3$ vertices, each $2$ of them are connected by edge). I think it should be number of edges or the degree for vertices but didn't find ...
0
votes
1answer
44 views

Number of arcs in a planar graph

I have graph built just like in the image: the red dots are the edges and the black lines are the arcs that connect them. The only difference from the picture is that in my graph the arcs are ...
3
votes
1answer
543 views

comparison of simplex and shortest path method

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the ...
0
votes
1answer
124 views

Isomorphism of Complete Graphs

I am struggling to understand the concept of isomorphism. By definition, if G and H are two simple graphs so that V(g) and V(h) are the number of nodes in G and H respectively, then isomorphism is ...
2
votes
1answer
158 views

Finding no-self-intersecting path in geometric graphs

Is there a polynomial algorithm to determine whether there exists no-self-intersecting path between given vertices $s$ and $t$ in a geometric graph $G$? Geometric graph is an image of a graph on a ...
1
vote
1answer
63 views

Ratio of vertices to edges when airplaines can fly from 1 of 4 cities to any other of the 4 cities

This is a true of false question: There are direct (nonstop) flights amount four cities that make it possible to get from any city to any other city by air. It follows that the beta index of the ...
0
votes
2answers
75 views

Can a graph with 3 vertices have a ratio greater than 1 of edges to vertices

A graph with three vertices has a beta index no greater than 1. A beta index of a graph is the ratio of number of edges to the number of vertices. The answer key says true but I think it's false. If ...
0
votes
1answer
56 views

Independence number

I know the independence number of a graph is the largest subset of vertices in a simple graph such that no two vertices are adjacent. I also understand the independence number of a Q3 graph is 4. What ...
0
votes
1answer
583 views

How to describe all normal subgroups of the dihedral group Dn? [duplicate]

The dihedral group consists of rotations and symmetries. But the symmetry group is a group only if n is even, thus the group of rotations is a normal subgroup of the dihedral group. So how to ...
0
votes
1answer
375 views

Probability of a node being connected to another

I am a newbie tinkering around with graph theory. Please pardon me for asking something very basic. Let us say I have a graph with n number of nodes. I have a binary adjacency matrix that specifies ...
0
votes
2answers
40 views

graph theory related to $k(G)$ problems

If $k(G) \ge n \ge 3$, show that every set of $n$ points in $G$ make a cycle. Where $k(G) :=$ Minimum number of vertices needed to remove such that the graph becomes disconnected.
0
votes
1answer
23 views

A formal procedure to successfully create a tree over $2^k$ vertices

I have a graph $G$ with $2^k$ vertices and initially zero edges. I am trying to successfully adding edges to end up with a tree with $2^k-1$ edges. Each time I add $2^{k-i}$ edges for $i={1,2,..,k}$. ...
1
vote
3answers
91 views

counting the number of paths from point $(0,0)$ to point $(n,m)$ on a recangular grid after N steps

Is there anyway to determine the total number of paths which start at the origin $(0,0)$ and finish at a point $(n,m)$ of a 2D rectangular grid after taking a total of N steps. On each step transition ...
1
vote
1answer
247 views

Uniqueness of doubly stochastic matrix descomposition

this is my first question in the site. Thanks in advance for all answers. It is well known that each bistochastic matrix can be represented as a convex combination of permutation matrices. I am ...
2
votes
1answer
233 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 ...
1
vote
1answer
104 views

Minimum a-z flow and minimum capacity a-z cut

Hi! I am working on a Graph Theory problem. I was wondering when finding flow paths are you allowed to have a path that goes against the directed arrow of the graph? I was wondering if I could have ...
2
votes
1answer
38 views

Let $T$ be a spanning tree. Prove that for cycles $C,D$, $E(C)\backslash E(T) = E(D)\backslash E(T)\implies C=D$

Let $T$ be a spanning tree of $G$. Prove that if $C$ and $D$ are cycles in G and $E(C)\backslash E(T) = E(D)\backslash E(T)$ then $C=D$. So far I have that if $e$ is an edge in $E(C)$ then either $e$ ...
5
votes
0answers
206 views

How is graph theory used to solve problems in number theory?

What are some applications of graph theory in number theory? How can a graph theory approach be useful to solving number theory problems? In general, is graph theory ever useful in making number ...
2
votes
1answer
315 views

Non isomorphic graphs - how to draw

I have been asked to draw all the non-isomorphic connected simple graphs, each with a degree sequence (2,2,3,3,3,3,4,4) I understand a non isomorphic graph is a graph where the relabelling of the ...