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

0
votes
1answer
17 views

How to understand the perfect binary tree formula?

I got this paragraph by reading "python algorithm", in which it mentioned `some knights participate in an knockout match, how many mathes do they need to produce the winner. It's answer says: I'm ...
1
vote
1answer
21 views

What's the 1-dimensional topology of a graph?

I'm reading through this paper here downloads.hindawi.com/journals/mpe/2013/815035.pdf where they say "Since a graph can be equipped with a topology to turn it into a a one-dimensional space, we can ...
6
votes
1answer
197 views

Probability of the existence of a path of a specified length between any tw0 vertices in a random graph

Let $G$ be a graph with $n$ vertices, whose average degree is $k$. What is the probability that between any two vertices, there exists a path of length at most $l$? NOTE: For the above problem the ...
5
votes
1answer
299 views

The number of paths on a graph of a fixed length w/o repeatings

Sorry for bad English. Consider a graph $G$ with the adjacency matrix $A$. I know that the number of paths of the length $n$ is the sum of elements $A^n$. But what if we can't walk through a vertex ...
0
votes
1answer
22 views

Labelled graph minor theorem

Note: this isn't duplicate to this: Does the Robertson-Seymour theorem apply to vertex-labeled graphs? One of equivalent definitions of graph minorship is the following: $G_1$ is minor of $G_2$ if we ...
1
vote
1answer
12 views

Chromatic polynomial of a graph $G$

Let $G$ be the graph in picture: calculate the chromatic polynomial of it. My attempt: I assume that $G(K_n,x)$ is the number of distinct colors of the complete graph with $n\geq1$ vertices with ...
0
votes
1answer
41 views

Algorithm for finding contradictions in a directed graph that represents implications

I need an algorithm that does this: For a directed graph where nodes represent boolean values and edges represent implication (implies TRUE and implies FALSE): If (arc exists between any ...
0
votes
0answers
34 views

Finding the smallest max eigenvalues for related matrices?

While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before. Suppose you have two symmetric $n$ x $n$ matrices in the form ...
2
votes
2answers
367 views

Dijkstra's Shortest-Path Algorithm

I'm presented with the following algorithm: Dijkstra's Shortest-Path Algorithm This algorithm finds the length of a shortest path from veftex $a$ to vertex $z$ in a connected, weighted ...
1
vote
1answer
125 views

Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
14
votes
2answers
285 views

Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
3
votes
0answers
24 views

A probability of a monochromatic cycle on a randomly colored lattice graph.

Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful" if and ...
0
votes
2answers
50 views

Determinant of identity minus adjacency matrix

Let $M$ be the adjacency matrix of a directed graph $G$. Is there any known relation between $\det(\textrm{id}-M)$ and the cycles of $G$? It is easy to see that if $G$ is acyclic then this ...
1
vote
1answer
30 views

proof of Konig's Theorem for bipartite graphs from Menger's Theorem

Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem? Konig's Theorem is as follows: For a bipartite graph $G$, the maximum size ...
0
votes
0answers
21 views

Determine the smallest integer n>1 such that there exists a connected graph G of order n such that |Aut(G)|=1? [on hold]

Determine the smallest integer n>1 such that there exists a connected graph G of order n such that |Aut(G)|=1?
-2
votes
0answers
17 views

Investigating the graph whose vertices are the subsets of an $n$-set and edges occur whenever two subsets intersect in exactly two elements. [on hold]

The $2^n$ vertices of a graph $G$ correspond to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two ...
3
votes
4answers
5k views

Checking whether a graph is planar

I have to check whether a graph is planar. The given type is $$ e ≤ 3v − 6 .$$ From Wikipedia: Note that these theorems provide necessary conditions for planarity that are not ...
6
votes
2answers
1k views

Degree of vertices in planar graph

Here is the problem: Let $G$ a planar graph with $12$ vertices. Prove that there exist at least $6$ vertices with degree $\leq 7$. Here it is what I did: Since $G$ is planar the number of its ...
2
votes
3answers
307 views

Multipartite graphs which are not planar

Please take a look at these definitions: A multipartite graph is a graph of the form $K_{r_1,\ldots, r_n}$ where $n > 1$, $r_1, \ldots, r_n\ge 1$, such that The set of nodes of the ...
3
votes
2answers
195 views

Planar graph, number of faces

I need to determine the number of faces of a planar graph with $n$ vertices, $m$ edges and $k$ connected components. I was thinking of using Euler's formula $f=m-n+2$ but that is for a connected ...
1
vote
1answer
73 views

proving that a graph is a planar graph

I looked at some problems where I had to prove that a graph is a planar graph. What methods are there to do this? For example: Is a 4-regular graph with 16 vertexes a planar graph?
8
votes
1answer
245 views

Bipartite graph: how many closed walk with given properties

Let be $G=(U,V,E)$ a bipartite graph where $U$ has $K$ possible vertices and $V$ has $N$ possible vertices. We focus on closed walks of length $2L$. Such walks can be described by the sequence of ...
5
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 ...
9
votes
2answers
453 views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
1
vote
2answers
41 views

Graph Degree and Some Condition

If $G$ be a Tree with degree $(5,r,s,1,1,1,1,1) $. (I wrote degree in non-increasing order). why all of this condition is True sometimes (I means on some condition)? I try to find an example that ...
0
votes
0answers
19 views

Let $g$ be a matrix corresponding to a directed graph so that $g_{ij}$ is the edge weight on an edge $ij$. How can we interpret $g^k$?

I know that if $A$ is a 0-1 adjacency matrix then $[A^k]_{ij}$ is the number of walks of length $k$ from $i$ to $j$. Does this generalize nicely? The reason for this question is to interpret a result ...
1
vote
1answer
18 views

Suppose that a planar graph has $k$ connected components, $e$ edges, and $v$ vertices. Also suppose that$\dots$

Question: Suppose that a planar graph has $k$ connected components, $e$ edges, and $v$ vertices. Also suppose that the plane is divided into $r$ regions by a planar representation of the graph. Find a ...
0
votes
2answers
28 views

Prove that $G$ is Hamiltonian.

Let $G=(V,E)$ be a connected graph which is not a tree. Prove that if for every cycle $C$ of the graph G and for any $v \in V(G)- V(C)$ there are more than $\frac{|C|}{2}$ edges from $v$ to $V(C)$ ...
5
votes
1answer
252 views

Disjoint paths on grid graphs

Let $f(G)$ be the smallest $m$, such that one can find $2m$ vertices in $G$ with the following property: pair up the vertices in any way, and find $m$ paths that join each pair. Then every set of path ...
3
votes
0answers
29 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
2
votes
1answer
67 views

What are the big issues in modern graph theory?

This is inspired by the similar question on modern set theory. I've read through the open problems in graph theory on Wikipedia's list of unsolved problems in mathematics, but what I'm looking for is ...
1
vote
1answer
56 views

Probability that the distance from some source vertex to any other vertex is at most exactly $l$ in a random graph?

Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$ and ...
3
votes
2answers
34 views

Prove that there is no bipartite graph on $14$ vertices with this degree sequence.

Prove that there is no bipartite graph on $14$ vertices with degree sequence: $$6, 6, 6, 6, 6, 6, 6, 6, 5, 3, 3, 3, 3, 3.$$ I assume a vertex with degree $5$ breaks this graph from being ...
2
votes
0answers
31 views

Counting symmetric binary matrices with constant line-sum

I'm trying to count, as the title suggests, symmetric matrices with entries $0$ or $1$ and constant line-sum $k$. ($0 \leq k \leq n$). If you start listing the number of these on a table you'll get a ...
0
votes
0answers
28 views

Number of walks in a Graph from u to v, containing exactly k edges

I have read here that if the adjacency matrix is represented by $A$, then the entry $A[i][j]$ in the matrix $A^{k}$ gives the number of walks from $i$ to $j$ containing $k$ edges. What is the proof ...
-1
votes
1answer
40 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
-3
votes
0answers
32 views

graph problem homework helps [closed]

1) Prove that if all edge-costs are different, then there is only one cheapest tree. (Hint: Do a proof by contradiction, following the proof of Kruskal’s theorem. Make sure to keep track of the costs ...
0
votes
0answers
16 views

Fint $N$ games played by minimal number of players

I got a following problem: There is a database which looks like this: $$\operatorname{GameId}||\operatorname{PlayerId}$$ $$1||1$$ $$1||2$$ $$\dots||\dots$$ where every game was played by 10 ...
2
votes
1answer
19 views

Non probabilistic algorithm for min-cut problem?

I know about Karger's algorithm and its variations, all of them being probabilistic. Is there non-trivial (i.e. non-brutefoce) deterministic algorithm for mincut problem?
1
vote
0answers
17 views

Gallai & Milgram path covers theorem from Diestel

I have a question about the theorem of Gallai and Milgram stating that every directed graph has a path cover $P$ such that one can make an independent set of $G$ by picking vertices from each of the ...
0
votes
0answers
20 views

Tree-width of a graph

What is the tree width of the graph? Here are the relevant definitions from my textbook: We define the width of an induced graph to be the number of nodes in the largest clique in the graph ...
35
votes
8answers
27k views

Online tool for making graphs (vertices and edges)?

Anyone know of an online tool available for making graphs (as in graph theory - consisting of edges and vertices)? I have about 36 vertices and even more edges that I wish to draw. (why do I have so ...
0
votes
3answers
210 views

Test for acyclic graph property based on adjacency matrix

I am trying to solve a problem that I have but I lack the theoretical knowledge that might be necessary to solve it. I have a directed graph encoded as an adjacency matrix. Is it possible to test ...
-1
votes
0answers
9 views

network design: why can't an almost satisfied proper function violated by all given sets?

I'm reading a book about (survivable) network design and i have a problem understanding a lemma. Given an undirected graph G and $V(G)$ its nodes and $E(G)$ its edges. The book defines a proper ...
2
votes
0answers
16 views

What does scale free mean in terms of a scale free graph

My understanding of a scale free graph is as follows: Say if we have a large graph $G$ if we were to take random partitions of $G$: $g1, g2,\dots$ Any centrality metric (such as page rank, degree ...
0
votes
1answer
37 views

Checking the correctness of the adjacency matrix for the given graph

I found the adjacency matrix for this graph; it is shown next to it. Is it correct?
6
votes
1answer
65 views

Where can I download the approx 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof?

Where can I download computer representations of the approximately 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof? The Wikipedia article ...
0
votes
1answer
69 views

Graph question concerning components.

Question Suppose that an undirected graph of order $n$ and size $m$ contains two vertices $s$ and $t$ of distance more than $n/2$. Show their exists a vertex $v$, not equal to $s$ or $t$, such ...
0
votes
0answers
25 views

Maximum length of any path from any root in a DAG

Let $\max \emptyset := -1$. For any directed acyclic graph $G = (V,E)$, let $f: V \to \mathbb{N}_0$ such that $\forall v \in V: f(v) = 1 + \max \{f(u): uv \in E \}$. Which terms are used for this ...
0
votes
0answers
24 views

Algebra on trees?

Given a forest of trees, I am interested in tree recombination operations that produce me a sub-forest spanned by some selected trees. To me, it somehow resembles space and spanned subspace in ...