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

-1
votes
1answer
28 views

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

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

Some problems on Graph [closed]

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
31 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
69 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
38 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
56 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
19 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
41 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
51 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
62 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
57 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
66 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
33 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
56 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
114 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
38 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'$ ...
1
vote
1answer
57 views

Help with proof that the union of two undirected cycle graphs is a cycle graph (with two edge deletions)

I am seeking advice on how to prove something. Apologies if my terminology is incorrect: I am not a mathematician. Let $G_1$ and $G_2$ be undirected cycle graphs with edges $E_{G1}$ and $E_{G2}$ ...
3
votes
2answers
64 views

Is the eigenvectors of vertex transitive graphs bounded

For a connected and regular graph $G$ with degree $ d $ at each vertex and adjacency matrix $A$, the normalized Laplacian of $G$ is defined as $L = I-\frac{1}{d}M$. Let $\psi$ be an eigenvector of $L$ ...
0
votes
2answers
34 views

I'm not quite sure I understand my book's reasoning for the answer

I have the following homework problem: Does there exist a graph, $G$, with 28 edges and 12 vertices, each of degree 3 or 4? First, my solution. $$ \sum deg(v_i) = 2 \cdot |E| \\ |E| = 28 ...
1
vote
1answer
23 views

Is the “smallest” connected graph with $n+k$ edges a trivial generalization of the “smallest” connected graph with $n-1+k$ edges?

Consider a set $P$ of $n$ points in the plane. Using $n-1+k$ line segments, $k\geq 0$, these points can be connected (i.e., the graph in which the points are the vertices and the line segments the ...
0
votes
2answers
32 views

Vertex/Edge Independence Proof

Show, for every connected graph $G$ of order $6$ with four independent vertices, that either $\alpha(G)=5$ or $\alpha'(G)\geq2$. I was thinking about using a contradiction proof. Any hints?
1
vote
3answers
62 views

Graph theory question (on Tournaments)

For a simple digraph, with a complete underlying graph (or a Tournament): $\text{in-degree}(v) + \text{out-degree}(v) = n-1$. Hence show that $\displaystyle\sum_{v \in V} (\text{indeg}(v))^{2} = ...
1
vote
1answer
47 views

creating all possible connected graphs with $n$ edges

Inspired by this question on Electronics, my question is: what is an algorithm for creating all possible graphs with a given number of edges but a possibly varying number of vertices? There is at ...
1
vote
0answers
39 views

Some questions on matroid

I have an unknown questions as follows. Thank you in advance. Let $M=(E,I)$ be a matroid and let $B$ and $B′$ be two disjoint bases of $M$. Let $B$ be partitioned into sets $Y_1$ and $Y_2$. Show ...
1
vote
1answer
51 views

Proof in Graph Theory

I have a $2D$ undirected graph of size $n \times n$ in which each node is connected to its four neighbours (left,right,top,bottom). If any general property is true for any nxn graph, what will be ...
0
votes
1answer
19 views

Sperners lemma how to mark internal vertices

Was reading sperners lemma from this http://www.math.hmc.edu/funfacts/ffiles/20001.4.shtml Couldn't understand certain things How to mark internal vertices? I could have mark some other number for ...
2
votes
1answer
67 views

The number of edges this graph

Let $G$ be a graph with $V(G)=\{d_i;d_i|n,d_i\not=1,n\}$ and $E(G)=\{d_id_j;d_i|d_j ~or~d_j|d_i\}.$ Here $n$ is the natural number.I know that if $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots ...
1
vote
1answer
21 views

In graph theory, are undirected graphs assumed to be reflexive?

In graph theory, are undirected graphs assumed to be reflexive? I know that in directed graphs vertices do not point to themselves unless explicitly stated, but what about undirected graphs?
4
votes
3answers
43 views

Making 7 vertices triangle free graph bipartite by deleting an edge

Can anyone assert or refute the following claim? Claim: In every triangle free undirected graph $G=(V,E)$, $|V|=7$, there exist an edge $e\in E$ such that $G'=(V,E\setminus\{e\})$ is ...
7
votes
2answers
33 views

The proof of $|I_X|=\frac{n!}{|\text{Aut}(X)|}$

Suppose $X$ is a graph with a set $V$ of vertices and $|V|=n$. $I_X$ is the isomorphy class of $X$ and $\text{Aut}(X)$ is the automorphism group of $X$. How can I prove the formula $$ ...
1
vote
1answer
30 views

Proving a lower bound for the traveling salesman problem

This link provides a guide for bounding solutions to the traveling salesman problem (TSP). In it, the author gives a lower bound on the optimal cost of any tour. For each vertex $v$ in the problem: ...
0
votes
1answer
21 views

how to define a function which returns a multiset

Given graph $G(V,E)$, how can I formally define function $f\prime$ which takes a node $v \in V$ and returns a multiset?
0
votes
2answers
19 views

Inequality regarding diameter, maximum order and number of vertices.

Suppose I have a connected graph on $n$ vertices with maximum degree $x$. What is the minimum value of the Diameter $D$?
0
votes
0answers
8 views

How to formally define a graph with attribute?

G(V,E) is the formal definition of a simple graph. How can we extend it to a simple graph in which each node has an attribute from a finite set S?
0
votes
0answers
28 views

Model a shortest path linear programming problem

I have a graph with 8 vertex, and i'm supposed to model a linear programming problem which consists in delivering 10 trash containers (1 is in vertex 1, 3 are at vertex 2, 2 are located at vertex 5, ...
0
votes
1answer
25 views

Finding two spanning graphs in a 4-regular connected graph

Prove if $G=(E,V)$ is a 4-regular connected graph then $G$ has two spanning graph $G_1(E_1,V)$ and $G_2(E_2,V) $ such as: $\mathbf 1.$ $\forall$ $v$ $\in$ $V$ in $G_1$ and $G_2$ $deg(v) = 2$ . ...
0
votes
1answer
33 views

How do I construct a minimum spanning forest?

I realize that a minimum spanning forest in a weighted graph is a spanning forest with minimal weight. Does this mean that I construct it by turning all of the trees into spanning trees?
1
vote
1answer
39 views

What is the difference between a forest and a spanning forest?

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree). If a graph is ...
0
votes
0answers
16 views

Matrix Representations of Chordal Graphs and Uses in Linear Algebra

Chordal graphs have the property of perfect elimination ordering. In Knuth's 2012 Christmas lecture ~1:12:10 he mentions that when the coefficients of a linear algebra problem can be written as a ...
0
votes
2answers
35 views

Planar complete tripartite graphs

For which values of $r$, $s$, and $t$ is the complete tripartite graph $K_{r,s,t}$ planar? Obviously I want to look for either a $K_5$ or a $K_{3,3}$ in order to show that a specific graph is ...