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

2
votes
1answer
154 views

Longest cycle containing two nodes

We're given a directed unweighted graph $G = (V, E)$, with $|V| \leq 100$. The purpose of this problem is to find the longest cycle containing the two nodes $a$ and $b$. Only the length of that cycle ...
8
votes
3answers
321 views

“Phase change” of a purely mathematical system

Every so often I hear people talking about "phase transitions" in purely mathematical or computer-science contexts, where there is no physics in sight. Today, for example, I heard some people talking ...
1
vote
2answers
68 views

Set Partitions and Graph Matchings

Is there a standard text on the theory of set partitions and/or graph matchings? (I ask both in the same question since it seems feasible that there might be texts containing information on both.) I ...
1
vote
2answers
252 views

Complete Bipartite Graph

I am trying to do this problem, but I don't see how it could be true. I think I have a counter example, but I am looking for confirmation. $P_n$ is the graph which is a path of length n. $C_n$ is the ...
2
votes
0answers
45 views

Properties of a generalized graph

I'll start with formulating my problem and then ask my question: To generalize a graph $Ga = (Va,Ea)$, we partition its nodes into disjoint sets. The elements of a partitioning $V$ are subsets of ...
0
votes
1answer
118 views

Construct a graph G for which the is-adjacent-to relation is antisymmetric.

Background: In this a graph is G=(V,E) where V is the set of all vertices and E is a set of 2-element subsets of V. For example: G=({1,2,3,4},{{1,2},{1,3},{2,4}}). E stands for edges similar to a line ...
2
votes
1answer
272 views

Proof involving a minimum weight spanning tree.

Please help with the following homework problem: Let G be an undirected graph, $v: E\to R$ and $w: E\to R$ be two weight functions on the edges of $G$. Let $z: E\to R$ be defined as the sum of ...
2
votes
0answers
89 views

Bounds on diameter of a graph

I'm looking for bounds on diameter of a given undirected graph with $n$ vertices and $m$ edges? Formally, I look to find $D_{min}$ and $D_{max}$ such that: $D_{min}\leq Diamter\leq D_{max}$ and it is ...
0
votes
0answers
121 views

What self dual 2D lattices exist?

The square lattice is a lattice that can be embedded on a 2D surface with no crossed edges. So I call it a 2d lattice. The dual of this lattice, for which every face becomes a vertex and every vertex ...
1
vote
0answers
108 views

Shortest path variation

I'm looking for a solution to the following problem, related to shortest path. You are given a directed Graph $G = (V,E)$, source $s$, targets $t_1, t_2, \cdots , t_k$ and costs $c_{ij}$ for ...
1
vote
1answer
203 views

Reference: Compendium of interesting graphs

I've been writing a little about some results on graph theory, and I want some nice examples of applying the results to some interesting finite connected graphs to show how the results might be ...
2
votes
1answer
433 views

Showing existence of a spanning tree in a graph with two kinds of edges using $k$ of one kind of edge

Given a simple1 undirected connected graph $G$ which has two kinds of edges, call them red edges and blue edges, I want to show that if it is possible to construct a spanning tree with exactly $\ell$ ...
1
vote
1answer
101 views

How many nodes before k-clique or k-anti-clique?

I am attempting to solve some problems here. For exercise 1, the tightest result I could get is $4^k$. Is that the mininum possible bound? I am trying to either find a tight example, or find a better ...
2
votes
1answer
65 views

Is there an unbiased random walk on a colored plane for any number of colors?

So I was trying to motivate the fundamental postulate of statistical mechanics (i.e. all microstates are assumed to be equally probable $-$ even if we can't practically measure them, but only their ...
1
vote
1answer
1k views

Radius and diameter of a line graph

Suppose I have a graph which is like this: A--B--C--D What is the diameter and radius of this graph? Here r = 1 and d = 3 and r < d/2 ..right ?
0
votes
1answer
153 views

Non-disjoint partition of a graph into cliques of bounded size

I am looking for a method to list cliques in a graph such that: All vertices of the graph are included in at-least one clique The size of every clique is no greater than a bound K The problem ...
8
votes
1answer
836 views

What is the number of bijections between two multisets?

Let $P$ and $Q$ be two finite multisets of the same cardinality $n$. Question: How many bijections are there from $P$ to $Q$? I will define a bijection between $P$ and $Q$ as a multiset $\Phi ...
1
vote
0answers
71 views

Increasing size of graph with respect to time

A graph $G(V,E)$ is growing with following rule: At every time step $t$, $An_t$ nodes are added to the graph. When choosing the node to which the new node connects to, we assume that the probability ...
1
vote
0answers
51 views

“Optimaly” reordering the vertices of a hypergraph.

I am not even sure of how to search for an answer to this, or how to approach the problem myself, so I thought I would try to ask it here. Consider an n-vertex hypergraph where the vertices are ...
2
votes
3answers
638 views

graph theory connectivity

This cut induced confuses me.... I dont really understand what it is saying... I am not understanding what connectivity is in graph theory. I thought connectivity is when you have a tree because ...
2
votes
3answers
374 views

Applications of the number of spanning trees in graphs

Let $G$ be a simple graph and denote by $\tau(G)$ the number of spanning trees of $G$. There are many results related to $\tau(G)$ for certain types of graphs. For example one of the prettiest (to ...
1
vote
3answers
353 views

Degrees of connected vertices and average vertex degree.

This is a problem inspired by Hard planar graph problem. Let $\nu$ be the average vertex degree of a graph $\Gamma$. Is it always possible to find an edge $\{u, v\}$ of $\Gamma$ such that $$\deg(u) ...
2
votes
1answer
493 views

Given an arbitrary number of points, how do you find an equidistant center?

Given an arbitrary set of points on a Cartesian coordinate plane, is there a generalized formula to find the closest point that is equidistant from all the given points? My first guess was finding ...
9
votes
2answers
1k views

Hard planar graph problem

Triangulation is called a planar graph in which every face is a triangle. Prove that in every triangulation exists edge $\left\{ u,v \right\}$ such that $\deg(u)+\deg(v)\le 22$. Give an example of ...
4
votes
1answer
292 views

Orbits of adjacency matrices under conjugation by permutation matrices.

(Disclaimer: I am new here, so be patient with my mistakes, but I welcome corrections, advice or comments.) I am interested in if anyone knows of ways of characterizing the orbits of an adjacency ...
1
vote
2answers
2k views

Hamiltonian Path Detection

Are there any special things to check to determine if a graph does not have a Hamiltonian Path. I know for a Euler Path you can check to see if there are any odd degrees or if the graph is ...
1
vote
1answer
119 views

Is there an existing graph that meets the following properties : disconnected, eulerian, hamiltonian and bipartite

A colleague of mine claims that there exists one, but I can't figure how an eulerian graph can be disconnected, since you have to visit all the graph vertices in the cycle...
0
votes
1answer
33 views

How do I approach this combinatorics problem involving labeled and unlabelled configurations

Here is the question: If we allow f(n) and g(n) to represent the number of labeled and unlabelled configurations, respectively, of n objects, then why is the following reasonable? You ...
0
votes
0answers
42 views

Independent maps in graphs

In graph theory What are independent maps? Do they differ between directed and undirected graphs? Are the following graphs I-maps? Would the answer be the same in case of undirected graphs? ...
1
vote
1answer
204 views

average distance in a graph

Having a graph of $n$ vertices in Euclidean $m$-dimensional space, is it possible to find average (Euclidean) distance between the vertices in $O(n)$ steps? Is there a deterministic algorithm for ...
1
vote
1answer
367 views

Graph Theory - Connectivity of r-regular graphs

Find the minimum positive integer r for which there exists an r-regular graph G such that λ(G) ≥ κ(G) + 2 I know it's not 1,2,3-regular since κ(G) = λ(G) for those graphs. All help appreciated.
1
vote
0answers
138 views

Estimation for ramsey number $R(3,k)$.

Previously I have shown that for any positive integers $k,l$, and any real number $p\in (0,1)$, ramsey number $R(l,k) \geq n- {n\choose k} p^{{k \choose 2}} - {n\choose l} (1-p)^{{l \choose 2}}$. Now ...
1
vote
1answer
99 views

Prove the following inequality: $N(P,P,2)\leq 4^{P-1}$

I've made very little headway on this problem, so any help is appreciated. Edit: Sorry, I should have explained that. In general, $N(p,q,2)$ is the smallest value of $n$ such that a red-blue ...
1
vote
1answer
43 views

Characterizations of operation that take a path and produce a star in a tree

I was looking at this operation in a tree, and try to relate it to the diameter of the tree. Pick a path of length $m$, so let it be $v_1v_2\ldots v_mv_{m+1}$. Remove all the edges in the path, and ...
1
vote
1answer
146 views

Question on the number of directed edges in a tournament.

I want to show that there exists $c>0$ constant s.t for any tournament on $n$ vertices there are two disjoint subsets A and B s.t: $$ e(A,B)-e(B,A) \geq c n^{\frac{3}{2}}$$ I know of the theorem ...
1
vote
0answers
184 views

A tree that does not satisfy: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$?

It is a strange question on a book. Give an example of a tree $T$ that does not satisfy the following property: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$. I ...
2
votes
1answer
96 views

Minimal Weighted Graph Paths?

Suppose we have a connected undirected graph with a positive integer cost assigned to each edge. Given two verticies, how do we find the set of minimal cost paths between those two nodes? Does this ...
6
votes
1answer
2k views

How to prove that a simple graph having 11 or more vertices or its complement is not planar?

It is an exercise on a book again.If a simple graph G has 11 or more vertices,then either G or is complement $\bar { G } $ is not planar. How to begin with this?Induction? Thanks for your help!
3
votes
1answer
319 views

Matching in a random graph

Hi can anyone help me? nothing I tried worked so far We build the following random graph: G=(L∪R,E) be a bipartite random graph when |L|=|R|=n. Each vertex v∈L chooses randomly and independently with ...
2
votes
3answers
1k views

How to determine the number of directed/undirected graphs?

I'm kind of stuck on this homework problem, could anyone give me a springboard for it? If we have $n\in\mathbb{Z}^+$, and we let the set of vertices $V$ be a set of size $n$, how can we determine the ...
4
votes
1answer
227 views

Spectral graph theory and connected components of graphs

We know that multiplicity of least eigenvalue of laplacian matrix of graph gives us number of connected components in graph.What is intuition behind this theorem? How do we know that this works in ...
3
votes
1answer
741 views

Is a 2-regular graph the same as a single cycle?

When I was doing some graph theory problem, came to my mind this corollary: Graph G is a single cycle if and only if $\displaystyle \forall_{v\in V[G]}\deg(v)=2$ I don't know whether I make ...
2
votes
2answers
120 views

Cycle in Graph with $Δ(G)\leq 10$

I have a graph named $G$. degree of each node in $G$ is at most $10$. I need to find an algorithm to determine that this graph has any cycle with length less than $20$ with $O(n)$ . I think it can ...
1
vote
1answer
287 views

Consensus in Discrete-Time and Matrix Theory [closed]

I have an $N \times N$ adjacency matrix $A_{ij}$ for nodes $i$ and $j$, numbered 1 through $N$. Each node $i$ starts with a scalar value $x_i(0)$ between 0 and 1. At each non-negative integral time ...
6
votes
2answers
3k views

Expected value of number of edges of a connected graph

There are n vertices. 2 vertices are chosen such that there is no edge between them and add an edge between them. We choose each pair with equal probability. Once we a have a completely connected ...
1
vote
1answer
357 views

Finding planar representation of graph

If it is known that a graph is planar, how do we find a planar representation of the graph? Is there any method other than trial and error? Thanks a lot.
0
votes
2answers
332 views

Subdivisions of graphs (must the vertices be distinct)

By Kuratowski's Theorem, A graph is planar if and only if it does not contain a subgraph isomorphic to a subdivision of K5 or K(3,3). My question is that for the subdivision of K5 (or K(3,3) formed ...
4
votes
1answer
499 views

Sum of the shortest paths in graph

Let $ d_{G} \left(x,y \right) $ be the length of the shortest path between the vertices $x$ and $y$ in graph $G$ and let $s\left(G\right) = \sum_{x,y \in V \left[G\right]} d_{G} \left(x,y \right)$ . ...
0
votes
3answers
543 views

Party problem / Ramsey's theorem R(3,3)

I'm looking for an algorithm that solve Party problem. The party problem asks to find the minimum number of guests that must be invited so that at least 3 will know each other or at least 3 will not ...
18
votes
2answers
477 views

Groups and generating sets

This question feels completely trivial and I am somewhat embarrassed to be asking it, but I am having a brain dead moment and failing to prove what I'm sure is a completely trivial statement about ...