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

7
votes
2answers
430 views

What is the Möbius analoge for Ihara's $\zeta$ function?

The Dirichlet series that generates the Möbius function is the (multiplicative) inverse of the Riemann zeta function; if s is a complex number with real part larger than 1 we have $$ ...
1
vote
0answers
13 views

Decompose a flow network into several trivial flows

Let $f$ be a flow in (a directed) network $G$. Show that it is possible to express $f$ as a sum of another flow $f_0$ which value is 0, and at most $|E|$ flows, each of which is trivial - i.e. flows ...
1
vote
1answer
281 views

Permutation matrix and simple directed graph

I have some code that works with simple directed graphs, but it is kinda slow. So I converted it to use an adjacency matrix instead of keeping a list of pairs of nodes. The code finds the ...
0
votes
0answers
17 views

Sparsifying a weighted complete graph

Sparsifying a graph $G=(V,E)$ using effective resistance method [as described in http://arxiv.org/abs/0803.0929 ], requires the existence of a Laplacian solver which can be used to calculate the ...
1
vote
2answers
2k views

Proving graph connectedness given the minimum degree of all vertices

I know that this is a repeat of a previous question asked with a similar title, but I didn't want to revive an old thread. The solution presented in that thread seems to be the common one, but I was ...
6
votes
1answer
80 views

$4$-regular graph with exactly one perfect matching

Can there be a $4$-regular graph with exactly one perfect matching? That is a graph that does have a perfect matching, but not two (not necessarily disjoint) perfect matchings.
0
votes
2answers
32 views

How to check if a digraph is strongly connected with its adjacency matrix?

Given a digraph G and its adjacency matrix A, which is the easiest way to check if it is strongly connected? In the case of an undirected graph I should check that the matrix $ ...
1
vote
1answer
54 views

Optimization problem on graph with weights on nodes and edges

I am solving a problem where I have a complete undirected graph with weights on the nodes and on the edges. The weight on the node represents a profit that you obtain if you select that node. The ...
1
vote
1answer
464 views

can someone tell me if this graph contains subdivisions of both K5 and K3,3

Can someone tell me if this graph contains subdivisions of both $K_5$ and $K_{3,3}$ or not? The graph G1134 is non-planar My thought is that this graph subdivision of $K_{3,3}$ but not $K_5$. Is ...
0
votes
0answers
35 views

Connectivity of a complete graph with one vertex

Consider the graph having just one vertex and no edges.I only know that it is 0-connected graph and every disconnected graph is 0-connected. So, I was wondering whether the graph K1 is connected or ...
0
votes
0answers
25 views

Kuratowski's theorem proof: Flappable bridges

I have a doubt concerning the proof of Kuratowski's theorem. The proof I am reading from is from Combinatorial Problems and Exercises by Lovasz. (Pg 299-301). We are given a graph $G$ which is a ...
1
vote
0answers
25 views

Finding the Chromatic Polynomial for the wheel graph $W_5$

Let $G$ be a graph and let $k \in N$. The chromatic polynomial $P_G(k)$ is the number of distinct $k$-colourings if the vertices of G. Standard results for chromatic polynomials: 1) $G = ...
0
votes
1answer
20 views

which algorithm is used to find a leaf in a tree?

If we have a tree $T$=$G(V,E)$. What is the best algorithm used to find the leaf? Is it DFS: Depth First Search ?
3
votes
2answers
50 views

prove that for any $k$-regular graph $G$, $\chi(G) \geq \frac n{n-k}$

This question is a part of another question that has two sections. In the first section I proved that for any graph $G$, $\frac n{\alpha(G)} \leq \chi(G)$ and $\chi(G) \leq n-\alpha(G)+1$. Now I ...
2
votes
1answer
33 views

How to prove that there is a monotone path in a graph with a length of greater or equal to average degree?

Let G be a graph with M edges, labeled by the numbers 1, 2, . . . , M. A monotone path is a path along which the labels of the edges create a monotone sequence. Show that there exists a monotone path ...
0
votes
1answer
28 views

proving $E \leq \frac{(n-k+1) \cdot (n-k)}{2}$

I'm trying to prove something about graph theory, but I'm not sure if I'm thinking in the right direction. Let $G$ be a simple graph, that is a graph without multiple edges and loops, let $n$ be the ...
0
votes
0answers
30 views

Show With High Probability $G_{n, p}$ has an induced path of length $(\log(n))^{1/2}$

The problem on which I am working states: Let the probability $p = d/n$ where $d > 1$. Show that with high probability, $G_{n, p}$ contains an induced path of length $(\log(n))^{1/2}$. My ...
0
votes
2answers
29 views

Every connected graph contains a spanning tree

If we consider two vertices connected by two edges, then this graph doesn't contain a spanning tree. Then what is wrong with the theorem?
1
vote
1answer
62 views

The four colour theorem

I have been reading about the four colour theorem and the fact that it is proved using a computer. My question is whether it is likely that we will ever achieve a proof without the use of a computer? ...
0
votes
1answer
22 views

Example for adjacency matrix of a bipartite graph

Can someone explain to me with an example how to create the adjacency matrix of a bipartite graph? And why the diagonal elements of it are not zero? Thanks.
0
votes
1answer
8 views

Graph theory: Proof that if the graph G(V1V2,E1E2) is conntected then the intersection (V1V2) is not empty.

I'm attempting to prove the following with contradiction. Unfortunately i'm not sure if my deduction is flawless in this one. Given: $G_1=(V_1,E_1),\quad G_2=(V_2,E_2),\quad G=(V_1\cup V_2,E_1\cup ...
0
votes
4answers
108 views

Books recommendation on Graph Theory (Beginner level)

What are some of the best books on graph theory, particularly for the beginners. Thank you.
0
votes
2answers
19 views

Given a forest, adding k edges would result in a cycle Proof

Assume you have a forest with k connected components. Prove that if you added $k$ edges, you would obtain a cycle. I’m thinking these facts/theorems may be useful... In a forest, each component ...
2
votes
1answer
26 views

Can you create non transitive dice for any finite graph?

Let's say you have a finite directed graph, with no two nodes that point at each other. Can we assign each node a dice, so that each node beats the node it is pointing at. This is easy for acyclic ...
1
vote
1answer
53 views

Eulerian and Hamiltonian cycles at the same time

I want to ask if it's possible for a graph to have both Eulerian and Hamiltonian cycles at the same time? And what will happen with graph's connectivity? Could connectivity k(G) be k(G) > 1 ?
1
vote
2answers
69 views

Grape/GAP algorithm for an isomorphic graph for a permutation

Problem: Given a graph G (as an adjacency matrix or a grape graph object), and a permutation $\pi \in S_n$. Find an isomorphic graph $G'$ as another adjacency matrix, under $\pi$. The concept is ...
1
vote
1answer
20 views

Show that there is a path of length k in G

Let G be a connected simple graph with $n \geq 3$ vertices. Suppose that there is a positive integer $k \leq n$ such that $d(u) + d(v) \geq k$ for every pair of non-adjacent vertices $u$ and $v$. Show ...
2
votes
1answer
356 views

Count ways to reach last layer

Consider directed graph which has $N + 2$ layers numbered from left to right by integers from $0$ up to $N + 1$. The leftmost ($0$) and the rightmost ($N + 1$) layers both contain only one vertex ...
0
votes
0answers
18 views

Prove that in any connected graph there is a closed walk which traverses each edge exactly twice

Prove that in any connected graph there is a closed walk which traverses each edge exactly twice. There is a nice solution by creating a new graph $G'$ in which we have replaced each edge of $G$ by ...
1
vote
2answers
1k views

Graph theory: If a graph contains a closed walk of odd length, then it contains a cycle of odd length

I am trying to prove what's on the title. I have been working on it for some time already and the problem I have is that I can't seem to prove that the cycle I get at the end is of odd length. Here ...
6
votes
2answers
94 views

Cubic Planar Graphs have $2^m-1$ Hamilton Cycles, contradicting Bosak…

I looked at the symmetric difference of hamilton cycle (HC) in cubic planar graphs and found that, together with the empty graph, they build a subgroup of the abelian group $\Omega$ of symmetric ...
1
vote
1answer
29 views

Finite graphs forms Fraïssé Class with limit Rado/random graph

I was reading Peter Cameron's explanation of Fraïssé's Theorem in his book Permutation Groups (Chapter 5). He states the Fraïssé class of finite graphs has limit being the countable random/Rado graph, ...
3
votes
1answer
29 views

How to perturb an adjacecny matrix in order to have the highest increase in spectral radius?

Let's suppose I have a generic directed graph $G$ and it's adjacency matrix $A$. I can add an arc wherever I want in the graph. (i.e. perturb the matrix A changing a single 0 into a 1). Where should ...
0
votes
0answers
12 views

Request: superposition of triangular lattice and its dual graph

Does anyone know where I could find a pdf of graph paper with both the triangular lattice and its dual hexagonal lattice superimposed? I'd like my students to have something they could easily doodle ...
3
votes
2answers
62 views

Show With High Probability, No Vertex Belongs to More than One Triangle

I am working on a random graphs problem, which is stated as follows: Suppose that $p = d/n$, where $d$ is constant. Prove that with high probability (w.h.p.), no vertex belongs to more than one ...
1
vote
1answer
30 views

Show that K and K' cannot both contain an Eulerian trail

For question (b), I understand how to prove that they can't both contain an Eulerian trail--eulerian trail exists if and only if there are no more than 2 odd degrees of the vertices. So for a ...
0
votes
0answers
19 views

Specific type of Eulerian cycle

Suppose i have a 4-regular planar graph, and furthermore suppose i pair the 4 edges incident to each vertex, so if $v \in V$ is adjacent to edges $\{e_{1},e_{2},e_{3},e_{4}\}$ i could for example pair ...
0
votes
0answers
18 views

Graph grouping with geometric criteria

I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are ...
0
votes
0answers
32 views

The size of the automorphism group of a graph

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et a. It is said on page 14 that the size of the automorphism group of a graph is either $1$ or ...
0
votes
2answers
27 views

Adjacency Matrix of a Graph Length of Paths Proof

Let A be an adjacency matrix of a graph G. Prove that the (i, j)th entry of $A^2$ is the number of paths of length 2 between vertex i and vertex j. *I know the adjacency matrix will be a square ...
0
votes
1answer
1k views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
0
votes
1answer
28 views

How to prove that Tree $T_1$ has a perfect elimination scheme (PES)

Give a tree graph $T_1$ =$(V,E)$ how can we prove that it has a Perfect Elimination Scheme :P.E.S P.E.S : is an ordering of the vertices, in such away that a vertex $v_i$ is simplical in the ...
0
votes
1answer
15 views

What's the complexity class of Sub-Polytrees isomorphism?

In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class. What about Poly-trees (oriented trees)? These are DAG's where the possible paths ...
2
votes
3answers
155 views

Graph Theory question?

Assuming that friendship is always mutual, prove that in any group of n  2 persons, there are at least 2 persons with the same number of friends in the group. How do I answer this question with a ...
0
votes
0answers
9 views

Min-cut of a graph using node set partitions

Denote the $x-y$ min-cut value by $g(x,y)$, can I always find a partition of the node set $V$ into three non-overlapping sets $A, B, C$ each containing $x,y$ and $z$ respectively, such that a $x-y$, ...
1
vote
2answers
39 views

How do I solve this problem from graph theory?

Say I have a graph G with n nodes and m edges. Give each edge a capacity. If I am working in discrete time intervals (say days), how do I find the fastest way to move x amount of product from a source ...
1
vote
0answers
14 views

eccentrcity of vertices in the given graph

I was calculating eccentrcity of vertices of the following generalized Petersen graph $P(15,2)$. For the vertx $u_0$, vertices $u_6$ and $u_7$ are farthest at a distance 4 and for the vertex $v_0$ ...
0
votes
1answer
27 views

Topology of network from adjacency matrix : honeycomb?

In a percolative problem, I have noticed that all of the nodes of my system are connected to 3 other nodes. I started drawing a bit and realized that this could look like a honeycomb lattice. The ...
1
vote
0answers
15 views

Graph with super nodes where each super node may have one or more sub-nodes in it

I have a question related to a problem I'm working on currently which is related to graph theory and complete sub-graph of size k (clique of size k). Let us say we have a graph where each node has one ...
-2
votes
2answers
42 views

Im stuck on this question..is there a formula for this? [closed]

"Suppose G is a graph with 19 vertices and 154 edges. Show that G is connected."