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
vote
1answer
43 views

Count number of k-cycles in complete directed graphs

Is there a closed formula to solve the total number of cycles of any length in a complete and directed graph (without loops)?
1
vote
1answer
47 views

Bipartite graph with $2 \times 10^{6}$ vertices, I need help with removing edges from the graph.

Let G be a bipartite graph. The number of vertices are equal to $2 \times 10^{6}$. Every node is of degree 10. We remove every edge with Probability $2^{-0,1}$. Show that the number of nodes after ...
1
vote
0answers
27 views

Prove that for every $k \geq 1$, there exist a connected graph $G$ of genus $k$

Prove that for every $k \geq 1$, there exist a connected graph $G$ of genus $k$ Here is what I think the proof should be. Let's represent $S_k$ as a regular $4k$- gon as following Define $H$ to ...
1
vote
0answers
11 views

Show that a comparability graph is perfect.

Show that a comparability graph is perfect. I'm trying to be able to prove Dilworth's Theorem from perfect graphs. I'll cite the perfect graph theorem for the complement step. This is the part ...
1
vote
0answers
95 views

Are there any programs like family echo that I can use to map mathematics?

Family echo is an online program that allows one to make a family tree, if nothing is clicked it shows most of the family tree as it is, but if one clicks a name one can see clearly all the ancestors ...
1
vote
1answer
83 views

Discrete math - Prove that a tree with n nodes must have exactly n - 1 edges? [duplicate]

I'm new in discrete math. Can someone prove simply that a tree with $n$ nodes must have exactly $n - 1$ edges. I have researched the solution but I haven't founded yet. I know of course, a tree with n ...
1
vote
0answers
58 views

What is the name of a graph structure with 'ports'?

I am wondering what the name of the following structure is. I might call it the madeup name "graph with ports" but most likely it already has a name that i am not aware of. The interesting thing to me ...
1
vote
1answer
24 views

Why can a set of edges of a bipartite graph with maximum degree d be partitioned in d matchings ?

In Wikipedia I read this: 'If there is a perfect matching, then both the matching number and the edge cover number are |V| / 2.' http://en.wikipedia.org/wiki/Matching_%28graph_theory%29 Is this the ...
1
vote
0answers
46 views

Expected size of largest connected component in a random k-out digraph?

Given a digraph with n vertices and kn edges, where each vertex has k out-neighbors randomly chosen at uniform without loops, how would I go about figuring out the expected value of the size of the ...
1
vote
0answers
47 views

Infinite connected graph such that every vertex has finite degree

Let $G=(V,E)$ be an connected graph with $|V| \geq \aleph_0$ such that $\text{deg}(v)$ is finite for all $v\in V$. Does this imply that $|V|=\aleph_0$?
1
vote
0answers
19 views

Generalizing interval graphs to higher dimensions

Not every graph is an interval graph, and that makes the notion of interval graph non-trivial. I was wondering whether the following generalization of interval ...
1
vote
1answer
83 views

Adjacency matrix and existence of triangle

Show that a graph $G$ contains a triangle (1) if and only if there exist indices $i$ and $j$ such that both the matrices $A_G$ and $A^{2}_{G}$ have the entry $(i, j)$ nonzero, where $A_{G}$ is the ...
1
vote
2answers
88 views

A problem about pigeonhole principle or graph.

Let $A=\{1,2,...,n\}$, where $\binom{n}{3}\geq n+1$. Let $A_1,A_2,...,A_{n+1}$ be distinct subsets of $A$ such that $\bigcup_{i=1}^{n+1}A_i=A$ and $n(A_i)=3$ for all $i$. How to prove or disprove that ...
1
vote
1answer
33 views

Show that we can check if $G$ has a circuit in time $O(V)$.

Consider a non-directed graph $G=(V,E)$ at which it is not allowed that we have edges of the form $(v,v)$. Show that we can check if $G$ has a circuit in time $O(V)$. According to my notes, we can ...
1
vote
0answers
54 views

Principal matrix, Ramsey theorem

Question: Let m be given. Show that if n is large enough, then every n-by-n 0, 1-matrix has a principal submatrix of size m in which all elements above the diagonal are the same, and all elements ...
1
vote
0answers
20 views

Can we know if the Eulerian path that is found in a directed graph is the only path?

I have a genome assembly assignment that reconstructs the genome using an Eulerian path on a de Brujin graph, but there could be multiple solutions, and I'm trying to guess how I would know if there ...
1
vote
0answers
37 views

Show bipartite graph with $m=4$ and $n=4$ is not planar.

I need to show that the 4,4-bipartite $K_{4,4}$ graph is not planar. However, I don't have a clue on where to begin. I figured a constructive proof would suffice, but how can I be sure that that ...
1
vote
0answers
12 views

Does a Matroid's graph not having 3-separation mean its dual doesn't have 3-separation?

Let there be a graph $G$, with a matroid $M(G)$. If there is no 3-separation in $M$, does it imply there isn't one in $M^*$? Any hints would be much appriciated!
1
vote
1answer
40 views

What is the relationship between genus and crossing numbers

I have some questions about topology graph theory and algorithms. Suppose given a graph with genus $k$ ($k\ge1$), if we want to draw this graph on the plane, there are at least $k$ crossing numbers ...
1
vote
0answers
54 views

Perfect matching in 3-regular graph.

Prove that each vertex 2-connected, 3-regular graph has a perfect matching. Please give some advice. Thanks in advance.
1
vote
1answer
62 views

Euler path in cube [duplicate]

Suppose we have the cube $3\times3\times3$ divided by $1\times1\times1$ cubes. We want to prove that there isn't path from an edge cube to the cube in the center which passes through every cube and ...
1
vote
0answers
34 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
1
vote
0answers
28 views

Choosing which sets of nodes are 'top' and 'bottom' in bipartite graph representations of real-world complex networks.

A bipartite graph is a triplet $G=(\top, \bot, E)$ where $\top$ is the set of top nodes and $\bot$ is the set of bottom nodes, and $E\subseteq\top\times\bot$ is the set of edges. Often real-world ...
1
vote
0answers
53 views

Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining ...
1
vote
0answers
29 views

Expected chromatic number

If $ G = (V, E) $ is an undirected graph where each edge is included with probability $ p \in [0,1] $ is there a way to calculate $\mathbb E[\chi (G)]$ using elementary methods? Or at least establish ...
1
vote
1answer
26 views

Is there a name for this graph density measure?

Let $G=(V,E)$ be an undirected graph. We define the following procedure (randomized greedy coloring): Fix some random ordering over the vertices (each permutation will be chosen w.p. ...
1
vote
1answer
41 views

MST or not without children ?

I've got an undirected weighted graph G with c:E(G)->IR. Now I want to find a spanning tree, such that a node v arbitrary, shall be an internal node, and among all spanning trees, in which v is only ...
1
vote
0answers
24 views

Strongly regular directed graph and its complementary graph..

I'm reading a paper (Art Duval) about generalizing the strongly regular idea to directed graphs.. anyway, the lemma is: Also, to be clear, the parameters are: n - number of vertices, k - valency, u - ...
1
vote
0answers
47 views

Is there any efficient progam or software to calculate the fractional chromatic number?

The fractional chromatic number $\chi_f(G)$ is a generation of the chromatic number of a graph $G$. It can be formulated as a linear programming question: Let $\mathcal{I}(G)$ be the set of all ...
1
vote
1answer
365 views

The number of e-even connected components of a graph

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question: A connected component of a graph is called e-even if the ...
1
vote
0answers
25 views

Plotting weighted nodes around a center

I am trying to plot nodes around a central node dynamically by weights of similarity. I have the weight of each node to every other node. I need to display the arrangement in such a fashion that it ...
1
vote
0answers
31 views

About the topology of a $d$-regular tree

What is the proof that the infinite $d$-regular tree is an universal covering space for any $d$-regular graph? Is it true that the infinite $d$-regular tree is a Ramanujan graph? (any easy way to see ...
1
vote
1answer
99 views

Photo Booth problem

There are $n$ people. There is a Photo Booth in which they can enter at most $m$ people at one time. They want to get a picture with all other person together. Please solve the $F(n,m)$; minimum ...
1
vote
0answers
43 views

biconnected graphs - st-numbering intution

Looking at this paper, the algorithm is done in two phases. First phase: Do a DFS search, compute the spanning tree with p[v] representing parent of v, compute the lowest ancestor (closest to the ...
1
vote
0answers
43 views

Expected Max Pseudotree Size

I'm working on a problem where I need to calculate the expected maximum pseudotree size in a randomly-generated pseudoforest with $n$ nodes. Expected maximum value is of course: $$ E(x) = ...
1
vote
0answers
29 views

Deviation of number of cycles of length 4 in Erdős–Rényi random graphs.

I'm working on my homework and can't find any relevant information for this problem. Problem: Let $G(n, p)$ be Erdős–Rényi random graph. I need to find deviation of number of cycles of length 4 in ...
1
vote
0answers
34 views

Inequality to bound $\sum_i a_i b_i - \sum_i c_i d_i$ (harmonic eigenfunction/graph) type sum with constraints

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus: $\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$ and wish to lower ...
1
vote
0answers
20 views

concerning Graph Theory/subgraphs/ even degree [duplicate]

Given a simple Graph $G=(V,E)$ ($V$ vertices, $E$ edges) I have to show that there exists a distribution $V= V_1 \cup V_2$ of the vertices such that all vertices in the induced subgraphs $G[V_1]$ and ...
1
vote
0answers
87 views

Induced cycle of odd length in a large graph

I'm trying to prove the following result in order to solve a different problem but I'm stuck; however I'm not sure if it is true, so I'll pose it as a question; Suppose we have a triangle-free ...
1
vote
1answer
55 views

Spectrum of infinite d-regular tree

Consider the adjacency matrix of the infinite d-regular tree, call it A. To find the spectrum we consider it as an operator in $L^2(V)$. It is stated that $A-\lambda I$ is always one-to-one. I do ...
1
vote
0answers
141 views

Proof of Hamilton Cycle in a Complete Bipartite Graph

For a complete Bipartite graph K(m,n) has a Hamilton cycle if and only if m=n. I want to know if the following proof technique is correct. My proof will consider using proof by contradiction. Assume ...
1
vote
0answers
25 views

Proof with chromatic index. [duplicate]

Prove that for $G = (V,E) $ $$ \chi(G) \chi(\overline{G}) \ge |V| $$ Please for some advices. Thanks in advance.
1
vote
0answers
31 views

What is $F_P$ and $E(P)$?

I'm reading Handbook of Graph Theory: At this section, he speaks about $F_P$ and $E(P)$. It's not really clear what they are. I guess there is enough context for someone to answer me but if ...
1
vote
0answers
24 views

Hypergraph coloring

I hawe the following task: Decide if all 4-uniform hypergraph with fourteen hyperedges can be colored with 2 colors. I think that the answer is yes, but how can i prove it?
1
vote
1answer
33 views

Every vertex in a caterpillar graph is adjacent to at most two non-leaf vertices

I am not sure about my proof that goes: Use induction on the number of vertex of caterpillar graph, C. Base case, C with n=1 holds since it is a adjacent to no vertex. So the claim holds. Inductive ...
1
vote
1answer
33 views

Graph theory, trees, show T is subgraph of G

Let T be a tree with n vertices. G be a non-empty graph with $\delta$(G) $\ge$ n-1. Prove that T is a subgraph of G. If it's a tree then I know it has to be connected and if the minimum degree is ...
1
vote
1answer
50 views

Calculating connected components in an undirected graph

Suppose that we have a graph $G$ with $n$ vertices and $n-k$ edges, such that it does not include any cycles. How many connected components does it have?
1
vote
0answers
63 views

Inequality in inverse Laplacian

I have the following problem, which is motivated by geometric diffusion on a directed graph. Conjecture. Let $A \in [0,1]^{n\times n}$ be strictly substochastic - i.e. $\forall i ~ \sum_j A_{i,j} ...
1
vote
1answer
43 views

Colouring graph's edges.

Let $G$ be a graph in which each vertex except one has degree $d$. Show that if $G$ can be edge-coloured in $d$ colours then (1) $G$ has an odd number of vertices, (2) $G$ has a vertex of degree ...
1
vote
0answers
17 views

Potentials and Markov Processes

Given a resistive electrical circuit $G$, i.e. a graph with nonzero weights attached to each edge whose reciprocal we call the "resistance," we can define a reversible markov chain on the graph, ...