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
1answer
191 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
1k 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
57 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
776 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
494 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
485 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
674 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
362 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 ...
2
votes
2answers
3k 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
142 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
35 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 ...
1
vote
1answer
221 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
513 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
147 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
100 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
157 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
204 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
103 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
3k 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
436 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 ...
4
votes
3answers
2k 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
267 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
964 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
121 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
436 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
4k 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
474 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
366 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
582 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
681 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
493 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 ...
3
votes
2answers
1k views

A graph with degrees 0 2 2 4 4 4?

Given a graph with 6 vertices of degrees 0 2 2 4 4 4, in what ways may it be drawn? Simple and connected or some combination of? Obviously it can't be connected due to the vertex with degree 0, but ...
5
votes
1answer
332 views

Graph with 10 nodes and 26 edges must have at least 5 triangles

This is not a homework question, but I would appreciate if people would treat this as if it were homework. I am looking for (nonspoiler) hints. I would like to prove that given any graph with 10 ...
1
vote
2answers
735 views

Find all the non-isomorphic graphs whose degree sequence is $(6,3,3,3,3,3,3)$

Sorry I'm new here, can someone please help me out with this question. I missed a couple of lectures and I don't even know where to start. I'm trying to find all the non-isomorphic graphs whose degree ...
0
votes
1answer
196 views

Shortest path with rotation costs.

There are dotes on the plane $(x,y)$ connected with directed edges. The distance $\rho(A,B)$ is standard euclidean: $|\overrightarrow{AB}|$. Except the distance cost we pay for rotation: $k\alpha$, ...
4
votes
3answers
327 views

If a graph of $2n$ vertices contains a Hamiltonian cycle, then can we reach every other vertex in $n$ steps?

Problem: Given a graph $G,$ with $2n$ vertices and at least one triangle. Is it possible to show that you can reach every other vertex in $n$ steps if $G$ contains a Hamilton cycle (HC)? EDIT: ...
3
votes
1answer
298 views

Algorithm to Find All Vital Edges in a Minimum Weight Spanning Tree

I am trying to locate an algorithm that can find ALL vital edges (edges whose deletion strictly increases the cost of the minimum weight spanning tree in the resulting graph) in a minimum weight ...
0
votes
2answers
1k views

Graph theory bipartite proofs with induction

I have this question I am given in a quiz and right away I did not even do it...I absolutely suck at induction as well as any kind of proofs. This question unfortunately had both...No matter what ...
1
vote
3answers
1k views

Graph with cycles proof questions

Two questions I'm stuck with: If C is a cycle, and e is an edge connecting two nonadjacent nodes of C, then we call e a chord of C. Prove that if every node of a graph G has degree at least 3, then ...
1
vote
1answer
41 views

Getting the formula of a live counter

I'm looking to replicate this greenhouse gases counter in my website. Poking around i found the initial data for the formula. The counter use the following information: Beginnig date: 2012/03/01 ...
1
vote
0answers
1k views

Dijkstra's Algorithm on a Directed Graph with Negative Edges Only Leaving the Source

I've been trying to figure out if Dijkstra's algorithm will always succeed on a directed graph that can have edges with negative weights leaving the source vertex only (all other edges are positive), ...
2
votes
0answers
764 views

Minimum Spanning Tree in a Complete Graph

We generate a complete euclidean graph by taking N random points from a limited (1.0 x 1.0 square) 2D space, connecting them all together (complete graph) and giving the edges weights proportional (or ...
13
votes
3answers
827 views

Counterexamples to proofs of correct statements

This question is in part inspired by a quote I saw in an answer to another question: The problem with incorrect proofs to correct statements is that it is hard to come up with a counterexample. ...
1
vote
1answer
345 views

Paths in a full graph

Given a complete graph with $4$ nodes, and one node is labeled $X$, find how many paths of length $N$ (might visit a node more than once) begin, end or both begin and end with $X$. This is not a ...
1
vote
0answers
56 views

Adding metric to matroids in order to describe graphs whose vertices are points in Euclidean space

My concern is about finding a mathematical model in order to describe graphs as combinatorial structures (with operations like edge addition, deletion and so on), and as elements in the Euclidean ...
1
vote
3answers
104 views

Matchings Containing Given Edges

Version 1 Is there a connected graph containing edges $e_1, e_2, e_3$ such that there is a perfect matching containing any two of the edges but no perfect matching containing all three? EDIT: ...
5
votes
5answers
8k views

Given a simple graph and its complement, prove that either of them is always connected.

I was tasked to prove that when given 2 graphs $G$ and $\bar{G}$ (complement), at least one of them is a always a connected graph. Well, I always post my attempt at solution, but here I'm totally ...