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
8 views

vertex magic total labelings

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
3 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
16 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
39 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
56 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
74 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
37 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
33 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
30 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
12 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
22 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
37 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
52 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
42 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
49 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
23 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
12 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
53 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
33 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
54 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 [on hold]

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 [on hold]

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
37 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
54 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
63 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 ...
1
vote
1answer
37 views

Counting triangles in triangular graphs

A triangular graph $T_n$ is the line graph of the complete graph $K_n$ (see for example here). Can you derive a formula for the number of triangles in the triangular graph $T_n$? If not, can you at ...
3
votes
1answer
54 views

number of spanning trees in this graph

This is a homework help, it ask us to find the number of spanning trees in this graph. I can use "matrix tree theorem" to solve it, but that means I need to compute the determinant of a $ 15\times ...
1
vote
1answer
100 views

Graph of a matrix

How to define the graph of a square matrix $\mathbf{G}$ with real entries? I know that given a graph $\Gamma(V, E)$, one can define its adjacency matrix $\mathbf{A}$. But given a matrix $\mathbf{G}$ ...
3
votes
1answer
36 views

Colouring bipartite graph with sets of possible colors to each vertex

I'm having some trouble with proving the following: Let $|S(v)|$ be the set of colours available to colour vertex v. The claim is that for every bipartite graph $G=(V,E)$, if $|S(v)| > log_2n$ for ...
1
vote
1answer
25 views

Given two spanning trees of a graph, shows edges can be traded between them to create 2 new spanning trees

The precise problem: Let $T$, $T'$ be two spanning trees of a connected graph $G$. For $e \in E(T)\setminus E(T')$, prove that there is an edge $e' \in E(T') \setminus E(T')$ such that $T'+e-e'$ ...