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
0answers
6 views

Chromatic Equivalence Requirements

I have searched and searched and am unable to find the answer that I am looking for. I am trying to determine the conditions required for two graphs to have the same chromatic polynomial. On both ...
2
votes
0answers
18 views

Maximum number of edges in a (n,n) bipartite graph, that doens't have a complete bipartite subgraph $K_{r,r}$

I need to prove that the maximum number of edges in a $n \times n$ bipartite graph, that doens't have a complete bipartite subgraph $K_{r,r}$ is lower bounded by $cn^{2-2/(r+1)}$ where c is a constant ...
1
vote
1answer
13 views

Power series convergence of random walk transition matrix

I would like to find out if $$ \sum_{t=0}^\infty P^t = \left( I- P \right)^{-1} ~,$$ where $P = D^{-1}W ~ $ is a random walk transition matrix. $W$ is a matrix describing weights in a graph and ...
1
vote
2answers
31 views

What is the difference between a simple graph and a complete graph?

I might be having a brain fart here but from these two definitions, I actually can't tell the difference between a complete graph and a simple graph.
2
votes
2answers
29 views

Proving corollary to Euler's formula by induction

I'm currently looking at two proofs to the following corollary to Euler's formula and I'm not quite seeing how the authors can make a specific assumption in their proof. One proof comes from my ...
-1
votes
0answers
15 views

vertex magic total labelings [on hold]

If G has a vertex-magic total labeling, then number of edges is more than equal to 2 time number of vertex/3
0
votes
0answers
6 views

Number of self-links, feedforward, feedback loops

Suppose we have a graph with N* nodes (N* is the number of internal nodes). Every directed link in the network exists with probability p. What would be the expected number of: self-links ...
1
vote
1answer
31 views

Prove that if graph $G$ is a 3-connected planar graph then its dual must be simple.

I'm trying to study for a quiz. I think I'm on the right track with this problem, however, I'm having a difficult time formalizing it. Prove that if graph $G$ is a 3-connected planar graph then its ...
1
vote
2answers
48 views

Combinatoric Graph [on hold]

Draw a graph whose nodes are the subsets of {a,b,c} and for which two nodes are adjacent if and only if they are subsets that differ in exactly one element? I'm having a really hard time understanding ...
1
vote
1answer
62 views

Bipartite Graph

Is there a bipartite graph with the following degrees: 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 6, 6? I've tried so many different combinations and I don't think there is a way to make a bipartite graph this ...
0
votes
1answer
75 views

When graph theory cannot model the most basic problem in wireless networks. Why?

I have a set of wireless links. These links are denoted by $\mathcal{L}=\{\ell_1, \dotsc, \ell_n\}$. Every link $\ell_i$ is composed of one transmitter $s_i$ and one receiver $r_i$. Initially, all ...
0
votes
2answers
38 views

Finite trees and embedding in infinite regular trees.

Assume that you have a finite tree $T=(V,E)$, where $V$ and $E$ are the set of vertices and edges of $T$, respectively. Let $d_{max}$ be the maximum degree the some vertice(s) $v\in{V}$. Assume also ...
4
votes
1answer
57 views

What's the number of possible structures of alkanes $C_n H_{2n+2}$?

When my chemistry teacher started listing out all possible structure of the hydrocarbon $C_7H_{16}$, my mind flied to look for a general formula. Let me mathematicalize this problem. Here, we have ...
0
votes
0answers
35 views

Graph planarity, Demoucron's algorithm

I need to implement Demoucron's algorithm for planarity testing and embedding. Testing is relatively easy to implement but embedding is the main problem. At some point, I need to draw some path ...
1
vote
1answer
35 views

Hamiltonian Paths in Complete Graphs

A bit of background to help explain the question: In a class we were given a large spreadsheet of stars and were asked to find two paths, starting from the Sun and visiting every star within 10 ...
-3
votes
2answers
25 views

Question over $0$-regular graphs [on hold]

Show that if G is a $0$-regular graph then $k(G)= \lambda (G)$ I know this to be true, but how do I show it?
0
votes
0answers
32 views

Independent set of edges contained in a maximum independent set of edges

Every independent set of edges in a graph is contained in a maximum independent set of edges I know this statement is true but how do I prove it?
0
votes
1answer
13 views

Proving minimum vertex cover

Every vertex cover of a graph contains a minimum vertex cover. I know the statement to be true but how do I go proving it?
1
vote
1answer
43 views

Is a butterfly network on 8-inputs planar?

I could prove that a four input butterfly network is planar. For that I simply drew it such that no two edges intersect. But I could not use the same approach for the 8-input butterfly network. So I ...
1
vote
1answer
23 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
2
votes
0answers
38 views

Uniqueness of projective plane of order 5

Is there a slick way to see the uniqueness of projective plane (equivalently, an affine plane) of order $5$?
0
votes
0answers
59 views

Prove that a certain graph and its dual are 4-colorable

Let $G$ be a simple planar graph with fewer than 12 faces. Suppose that each vertex of $G$ has degree at least $3$. prove that $G$ and its dual are 4-colorable. I'm not too sure how to approach ...
0
votes
2answers
43 views

What is the difference between maximal flow and maximum flow?

I have tried a lot on internet, but I am unable to get a good answer on the difference between maximal and maximum flow in case of network flow. Anybody has an idea? with example would be really ...
0
votes
1answer
20 views

uniqueness of Maximal Independent Set(MIS)

Is maximal independent set of a graph unique? I think between indepent sets, only one of them is maximal. So does it prove that MIS is unique?
0
votes
1answer
23 views

How many isomorphisms do these iso classes of 5 edges and 5 vertices have

Hello, I am referring to the second and third graphs. The second graph should have 60 isomorphisms but I can't see how. I thought it should be (5 choose 1) for a and then (4 choose 2) for the ...
1
vote
2answers
25 views

Graph theory maximum cardinality?

describe an algorithm that finds as efficiently as possible a matching of maximum cardinality in any bipartiate graph I know that matching means that in the graph no two edges share a common vertex. ...
0
votes
2answers
61 views

what is the maximum number of non loop edges that can exist in an undirected graph

please tell me a equation to find maximum number of non loop edges that can exist in an undirected graph. for example if vertices are 10 then how many non loop edges can exist?
1
vote
1answer
24 views

How many automorphisms does the second graph have

Hello, the second graph should have 2 automorphisms, but I see that none of the vertices has exactly the same adjacent vertices, so that I would be able to switch them and form an automorphism. What ...
0
votes
1answer
13 views

Discrete math on multipartite graph

I am wonder about these problem 1.The complete Multi-partite graph $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$ 2.the number of edge of $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$
-1
votes
1answer
27 views

How many different binary search trees can be made with three pieces of data? [on hold]

This is for a discrete math course, not computer science.
0
votes
0answers
25 views

Some problems on Graph [on hold]

I have some difficult problems. I would like you to give some ideas. Thank you in advance. Let $G = (V;E)$ be a connected graph with $n$ vertices and $m$ edges. Consider the set $W$ of all spanning ...
0
votes
1answer
27 views

How many isomorphic graphs does this iso class of 5 vertices and 5 edges have?

I am referring to the second graph. It has 60 graphs, but I can't seem to understand why. What i have so far is that there are (5 choose 2) ways of picking b and d combo; but what do I times this by ...
-1
votes
0answers
20 views

how many simple graphs of 5 vertices and 5 edges [duplicate]

This class has 4 automorphisms and 30 isomorphisms, so the total number of graphs is 120. But the formula I have for simple graphs says that the total number of graphs is (possible edges choose ...
0
votes
1answer
24 views

Please explain why this isomorphic class has 30 graphs and 4 automorphisms

Please explain why this iso class with 5 vertices and edges has 30 graphs and 4 automorphisms. I understand there are 5 ways to choose a, but then where does 4 choose 2 come in? Please help. This is ...
2
votes
1answer
26 views

Forbidden toroidal minors

A finite graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor. Is there a (finite) set of minors that can classify if a graph is toroidal?
1
vote
2answers
28 views

Edge-Connectivity of a graph

If $G$ is a graph of order $n$ such that $\delta(G) \geq (n-1)/2$, then $\lambda(G)= \delta(G)$ So I know this statement to be true. How would I prove this statement?
0
votes
0answers
58 views

Matrix graph and irreducibility

How do I prove that if $A\in\mathbb C^{n\times n}$ is a matrix then it is irreducible if and only if its associated graph (defined as at Graph of a matrix) is strongly connected?
0
votes
2answers
34 views

Given a directed graph, count the total number of paths of ANY length

Given a directed graph, how to count the total number of paths of ANY possible length in it? I was able to compute the answer using the adjacency matrix $A$, in which the number of paths of the ...
2
votes
1answer
55 views

Algebraic Combinatorics

Let $K_{r,s}$ denote the complete bipartite graph, defined on $r + s$ vertices $\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between $v_i$ and $w_j$ for $1 ≤ i ≤ r$ and $1 ≤ j ≤ s$. By ...
1
vote
0answers
27 views

Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ...
0
votes
1answer
23 views

edge chromatic number of regular graphs [closed]

prove that a graph G that is k-regular and exactly n vertices which n is odd ,has the index chromatic number of maximum degree.
-2
votes
0answers
19 views

Data mining of networks represented as graphs [closed]

What are the main tasks and methods in data mining of networks represented as graphs?
0
votes
0answers
18 views

questions on rooted forest

Let $D = (V;E)$ be a connected directed graph and let G be its subjacent graph. Let $I_1$ be the family of independent sets of the graphic matroid $M[G]$. Let $I_2$ be the collection of subsets $Y$ E ...
1
vote
1answer
39 views

Random Graphs: Examples of their Uses

Just writing a paper at the moment on random / random geometric graphs. If any of you could perhaps give examples, as broad and interesting as possible, of where these have been used across science? ...
0
votes
0answers
9 views

Random walk betweennes for directed networks

I have been researching the random walk betweenness method for undirected networks following, A measure of betweenness centrality based on random walks, M. E. J. Newman, Social Networks 27, 39-54 ...
1
vote
0answers
44 views
+50

Does any vertex transitive graph have a bounded eigenvector?

Following up on the negative answer to this question, I would be interested in knowing the answer to the following question, which I cannot seem to find an obvious contradiction to when testing for ...
0
votes
1answer
59 views

P, NP-Complete and NP-Hard Problems

I have confusion over P, NP-Complete and NP-Hard problems. I understand a polynomial time algorithm is one which can be solved for a an input string of length n. But why would a problem not be in ...
0
votes
0answers
56 views

Proving The Diamond Lemma

We have the diamond lemma as follows: Let $\rightarrow$ be relation on a set $P$. Let $\twoheadrightarrow$ be the reflexive transitive closure of $\rightarrow$ and $\sim$ the equivalence relation ...
0
votes
1answer
65 views

How to determine number of isomorphic classes of simple graph with n vertices, each with degree m?

For HW, I need to find the number of isomorphic classes of a simple graph with 7 vertices, each with degree two. I know I could brute-force it by finding all edge sets that fulfill that criteria, but ...
0
votes
1answer
31 views

Min-Cost-Flow Problem

Given a directed graph $G = (V,E)$ with a cost function $\gamma: E \to \Bbb R_{\geq 0}$ and two vertices $u,v \in V$. How to reduce the problem of finding a directed path from $u$ to $v$ with minimum ...