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

Graph theory : How to find edges ??

A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph. We denote by Kn the complete graph on n vertices. A simple bipartite graph with bipartition ...
1
vote
0answers
35 views

Distance matrix of connected graph always invertible?

I know there's a question elsewhere about distance matrix for points on Euclidean plane, but I'm not sure if that one was relevant. Anyway, given a connected (simple) graph G with $n$ vertices ...
0
votes
1answer
25 views

What are some non planar graphs whose sequence is $(4\,4\,3\,3\,3\,3)$?

I know that in order for the $6$-vertex graph to be non planar, it needs to contain more than $12$ edges. I tried drawing some picture to find the graph, but run out of ideas. It's easy to find the ...
1
vote
0answers
21 views

automorphisms of the infinite trivalent tree

Let $T$ be the infinite trivalent tree. I want to show that if $\alpha,\beta,\alpha',\beta'$ are vertices of the tree such that the distances $d(\alpha,\beta)$ and $d(\alpha',\beta')$ are equal, then ...
-1
votes
0answers
20 views

Graph Theory: Bipartite

Show that a bipartite graph G has a perfect matching if and only if |N(S)|≥|S| for all S⊆V. I am having trouble getting this problem started. Could someone help me with this please. Thanks
1
vote
1answer
32 views

Bounds on the size of the arc set of a directed graph which is connected but not strongly connected

An exercise in Introduction to Graph Theory by Robin J. Wilson asks for a proof that, if $D$ is a simple directed graph with $n$ vertices and $m$ arcs which is connected but not strongly connected, ...
0
votes
0answers
13 views

Detect Regions Described By Lines in Rectangular Coordinates

Need some help from the superior math minds here. This problem is part of a software project. Essentially, I have a Cartesian grid. The user can create lines by plotting points (every 2 points ...
0
votes
1answer
44 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
0
votes
1answer
22 views

Geodesic distance in graphs

I'm reading a paper that deals with networks/graphs. In the paper they mention the term 'geodesic distance'. I'm not able to understand what does it mean. I hope if you can explain it to me.
0
votes
1answer
26 views

find an algorithm to find MST in linear time while each edge has the same weight

I have been disscussing this problem with a lot of my friends . However no solution has been found. let G= w is a weight function for each e in E w(e)=1 find MST of G in O(|V|+|E|) thanks
0
votes
1answer
34 views

Calculating Adjacency Matrix

I'm having trouble understanding the concept, I know it is pretty simple but could someone help me out. Assume that I have the following: $V = \begin{bmatrix} 0&0&1 \\ 0&0&1 \\ ...
0
votes
1answer
72 views

Similar to star-comb lemma but finite graphs

The famous star-comb lemma for infinite graphs states that if $S$ is a infinite set of vertices in a connected graph $G$, then $G$ contains either a comb with all teeth in $S$ or a subdivision of an ...
1
vote
1answer
22 views

Expectation value of number of cycles in a random directed graph

Suppose you have a random directed graph with N vertices and a probability p that there is a directed edge between any two ordered pairs of vertices. Does there exist an exact formula or an upper ...
0
votes
0answers
18 views

Partition of the node set of a graph into connected subsets

What word is most commonly used in graph theory for a partition of the node set of an undirected graph into connected subsets? More rigorously: Given an undirected graph $(V,E)$, a partition $S ...
2
votes
3answers
1k views

In graph theory, what is the difference between a “trail” and a “path”?

I'm reading Combinatorics and Graph Theory, 2nd Ed., and am beginning to think the terms used in the book might be outdated. Check out the following passage: If the vertices in a walk are ...
-1
votes
0answers
14 views

A Separable graph on 4 vertices

Can we construct a nonseparable graph on 4 vertices each vertex of which has degree at least four and at least two distinct neighbours, and in which splitting off any two adjacent edges results in a ...
7
votes
0answers
152 views

Genus of the graph $K_{4,2,2,2}$.

What is the genus of the complete $4-$partite graph $K_{4,2,2,2}$? What i know: Since $K_{4,4,2}$ is a subgraph of $K_{4,2,2,2}$, and genus of $K_{4,4,2}$ is 2, $K_{4,2,2,2}$ has genus greater than ...
0
votes
0answers
33 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition ...
1
vote
0answers
28 views

Random walk on a graph

For a random walk say from point $x$ to $y$ on a graph, How is the probability of a Random walker reaching point $y$ before returning to $x$ related to the expected of the number of visits to point ...
1
vote
3answers
45 views

Error for graph Theory proof

I am looking for an error in the proof but I am not certain about it. Pretty sure it has something to do with how there is not always a cycle of length 3. Theorem 1. For every (undirected) graph ...
0
votes
1answer
83 views

What is the name of the symmetry of a bracelet transposition?

Take a bracelet with colored beads on it. Normally two bracelets belong to the same equivalence class under rotations and reflections. For an example, consider the bracelet denoted by the word ...
1
vote
1answer
80 views

Proof that G - v is a tree

For school we have the following assignment: Let v be a leaf of graph G. Prove that the following two statements are equivalent: (i) G is a tree, and (ii) G - v is a tree. The first thing I ...
0
votes
0answers
23 views

Is there a special name for a k-connected component that is not k+1 connected?

When removing all bi-connected components from a graph I'm left with a number of connected components, but they are also not bi-connected. Is there a special name for those components?
0
votes
1answer
25 views

Degeneracy number of a ring graph

The definition of $k-$ degeneracy is not clear to me. Could someone please explain how is degeneracy number different from maximum degree $\Delta G$ of the graph $G$? And second question is, does a ...
0
votes
2answers
50 views

Partition Graph

I need to find partition (S) (with more then 2 nodes) of a non-oriented graph (G), that containes no more than two nodes connected with the rest of graph (G \ S) I could invent an algorithm of brute ...
0
votes
1answer
23 views

Show that cubic hamiltonian graph is edge-3-colourable.

How can I show that cubic hamiltonian graph is edge-3-colourable?
0
votes
1answer
43 views

Probability of random walk traversal

Consider a random walk on an connected, non-bipartite, undirected graph G. Show that, in the long run, the walk will traverse each edge with equal probability. Note: The walk can traverse each edge ...
1
vote
1answer
60 views

Why can't a Meredith Graph be Hamiltonian?

I need to find out why Meredith Graph is not Hamiltonian Meredith Graph is so complex to analyze in this regard. Can anyone help me wih their expertise?
0
votes
1answer
22 views

A Graph in which subgraph is on Hamiltonian is Hamiltonian? [duplicate]

If a Graph has a sub graph which is not Hamiltonian, Will the Original graph also non Hamiltonian? For Example, K3,4 is not Hamiltonian. What is I connect 10 K3,4 graphs in a way to makeup Meredith ...
1
vote
1answer
53 views

Number of ways to surround the origin with a chain on the discrete grid

I have a 2-D square lattice and I am interested in finding the number of chains (series of squares) that I can surround the origin with. the length of the chain is from 4 to lets say to 10 squares. I ...
0
votes
0answers
30 views

Illustrate this proof about transversals with an example. Is there a typo?

Let $F = \{S_1,\dots,S_m\}$ and $G = \{T_1,\dots,T_m\}$ be two collections of subsets of a finite set $E$. A transversal for $F$ is a list of elements $s_1,\dots,s_m$, one coming from each set in ...
0
votes
0answers
17 views

Tradeoff between graph diameter and graph connectivity

Let $G$ be a graph with the property that, for every node, no more than $n^b$ nodes lie within distance $n^d$ of that node. Can we use this information to infer that the graph diameter (max distance ...
2
votes
1answer
36 views

A tree graph - find how many pairs of vertices, for which the sum of edges on a path between them is C

I've got a weighted tree graph, where all the weights are positive. I need an algorithm to solve the following problem. How many pairs of vertices are there in this graph, for which the sum of the ...
0
votes
0answers
20 views

Calculating Cartesian product of matrix

I don't know why I'm struggling to work this out. I'm reading a paper on Algebraic Graph theory and come up with this problem. $x_{i} \in \Re^{d}, i = 1, ....., N$. Let $V = {1, ......, N}$ Where ...
1
vote
1answer
25 views

The vertex covering of a graph that has isolated vertices

I know the theorem that in a graph G=(V,E) which has no isolated vertex, a set $C\subset V$ is a vertex covering in G if and only if the set V‐C is an independent set in G. I want to know whether this ...
1
vote
2answers
33 views

How do I find the adjacency matrix for the nodes of an n-dimensional finite grid?

I have an orthotopic grid, in n-dimensions (usually small ~<3), where each node is connected to it's orthogonal neighbours. The grid may be any number of nodes long, but is finite (and usually ...
0
votes
1answer
52 views

Find eigenvalues from a given relation.

This is a simple problem of linear algebra. One without knowing graph theory may solve it. I am missing a small easy logic. Description: Let $G$ be a graph with $n$ vertices and $G^c$ is its ...
4
votes
1answer
457 views

How to prove the Mantel's theorem of graph theory 's bound is best possible?

The theorem state that every graph of order $n$ and size greater than floor function $\lfloor \frac{n^2}{4} \rfloor$ contain a triangle. I already know a proof of the number of the edge of graph ...
0
votes
1answer
38 views

Shortest distance matrix given an adjacency matrix?

If I have an adjacency matrix, how can I find a matrix that has the shortest distance between each pair of nodes? (distance matrix, but the nodes are not in a euclidean space) I'm trying to implement ...
1
vote
1answer
28 views

Simple crossing number question

How can I prove that $K_{1,2,2,2}$ has a crossing number of 3? I have an example of a it with 3 crossings, now I need to prove that it cannot have only 2 crossings. My guess is that: Suppose ...
1
vote
0answers
13 views

Algorithm for Simple Graph Given Degree Sequence [duplicate]

Are there an algorithm that provides a fastest way to construct simple graph given a degree sequence? Are there any other interesting problems around this area that I might be overlooking and should ...
1
vote
0answers
31 views

Upper bound for constant weight code L(n,d,w), with n=128, d=4

I would like to find an upper bound: L(n,d,w) <= f(n,d,w) for a constant weight code L(n,d,w), where w is the maximum weight, d is the Hamming distance between codes, and n is the code length. I ...
3
votes
1answer
47 views

For which chess boards do solutions exist for this generalised Knight's Tour problem?

We know from a theorem by Schwenk that for any (m x n) chess board with $m \leq n$ it is always possible to create a knight's tour unless one or more of these three conditions are met: m and n are ...
0
votes
0answers
20 views

how to calculate the minimum edge cut set number of a graph

Given a graph, there are several kinds of minimum edge cuts. How to calculate how many cuts in the minimum edge cut set? Is there any algorithm solving this problem? Thank you!
0
votes
0answers
18 views

Multiple Attachment to the Same Node in Barabasi-Albert Model

In the Barabasi-Albert Model, is a newly introduced node allowed to attach more than once to the same node? The master equation does not seem to include terms describing nodes gaining more than one ...
3
votes
0answers
70 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being ...
1
vote
0answers
45 views

2 simple doubts about graph theory problems

The first one: In this exercise I am asked to compute the number of 4-regular graphs of order 7. I had an idea but I don't really know if it is the correct way of proceeding: In a graph of order 7, ...
2
votes
0answers
65 views

Out of all combinations (n,k), largest set such that each combination overlaps with others by d or less.

This problem is relevant to determining the number of discriminable combinations of components in a sensory perception task. Suppose that there are N components to choose from, and we are only ...
0
votes
1answer
293 views

Proof of Sperner's Lemma

I am looking for a concise and mathematically robust proof of the Sperner's Lemma. The easiest proof I found so far is Math Pages Blog, but I don't get it without few details. Following is the proof ...
1
vote
2answers
22 views

Modeling properties of a graph?

There is an undirected graph modeling highways in Texas, the vertices are cities and the edges are highways. How would you model the property. "Even if you shut down one highway, you can get from any ...