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
0answers
16 views

Planar Graph Isomorphism

In 1980, I. S. Filotti & Jack N. Mayer proved planar graph isomorphism testing could be done in polynomial time. Does anyone have an implementation of that? I have a few billion planar graphs ...
0
votes
1answer
11 views

Degree of a self-complementary graph with $4k+1$ vertices

How can we prove that every self-complementary graph on $4k+1$ vertices has a vertex of degree $2k$ ?
0
votes
0answers
8 views

definition clarification of graph embeddings

Recently I started reading graph embedding. But I am unable to grasp its definition from wikipedia. Can anyone explain this term with an example. I will be really thankful. Thanks.
-3
votes
0answers
34 views

What is the use of Euler paths?

In real life what are the use cases of Euler paths ? A path in a multigraph $G$ that includes exactly once all the edges of $G$ and has different first and last vertices is called an Euler path. ...
1
vote
0answers
7 views

Graphs from which their feedback vertex set has been removed

I am reading Vazirani's book "Approximation Algorithms". It is legally available online here. On page 56 (74 in the pdf), I have a question regarding the claim at the bottom of the page: Clearly, ...
0
votes
0answers
12 views

Problem on costructing flows in a network with multiple sources and sinks

Problem : Formulate and prove a theorem that gives necessary and sufficient conditions so that a network with multiple sources and sinks has a flow that simultaneously meets all prescribed demands ...
0
votes
0answers
6 views

n-regular hypergraph and its resolution

Let $G =(V(G),E(G)))$ be a $n$-regular hypergraph. Let $Z_n$ be a cylic group with generator $a.$ Definition : A resolution of $G$ is finite partially ordered set $C$ with $C_0$ is the set of ...
0
votes
0answers
27 views

Is there a graph that satisfies these properties in Euclidean space?

There are finitely many points. Any two different points is connected by a unique line. Any two different lines intersect on a unique point. There are four points such that any three of them do not ...
0
votes
1answer
13 views

Show that this construction preserves connectedness

Let $G_1$ and $G_2$ be $k$-connected graphs and let $v_1\in V(G_1)$ and $v_2\in V(G_2)$ be such that $\deg v_1=\deg v_2=k$. Form a new graph, $H$, by putting an $M$-matching of size $k$---conneect ...
0
votes
0answers
10 views

Fill valleys of waveform (flatten them, level them out)

I have waveform data and want to fill the valleys with a given maximum width. That is, I have sample values with a constant distance. The parameter "maximum width" determines the y-position of the ...
-1
votes
1answer
32 views

Adjacency table, directed graph [on hold]

The following adjacency table for an undirected graph G is missing info. How can you detect that it cannot possibly be complete? Correct it by adding the minimal possible extra info, then determine ...
0
votes
0answers
9 views

Intuition behind eigenvector centrality and computation procedure

There are various metrics that are used in social network analysis to estimate/find the influence of a node. Among them are various "centralities" - betweenness centrality, closeness centrality and ...
2
votes
2answers
34 views

Number of spanning trees in a complete split graph

A graph is a complete split graph if we can partition it into an independent vertex set and a clique, such that every vertex of the independent vertex set is adjacent to every vertex in the clique. ...
3
votes
1answer
20 views

Use Tutte's synthesis to prove that the Harary graph $H_{3,n}$ is 3-connected $\forall n>4$.

Use Tutte's synthesis to prove that the Harary graph $H_{3,n}$ is 3-connected $\forall n>4$. I thought I could prove this by induction; I was able to prove the base case $(H_{3,4})$, but I ...
0
votes
1answer
19 views

Find and prove some needed conditions on $m,n$ for the complete bipartite graph $K_{m,n}$ to have…

Question: Find and prove some needed conditions on $m,n$ for the complete bipartite graph $K_{m,n}$ to have: An eulerian circuit. A hamilton cycle. Attempt: I've conjectured that ...
-10
votes
0answers
44 views

Is there a link between music theory and the mechanics of the universe? [on hold]

The production(formation)[death] of a chromatic(spherical)[gravitational] piece(droplet)[star] of music(liquid)[space/time] minimizes the tonal-area(surface-area)[dimensions] which is the ...
0
votes
1answer
34 views

Is it possible disconnected graph has euler circuit?

I have doubt ! Wikipedia says : An Eulerian graph is one in which all vertices have even degree; Eulerian graphs may be disconnected. What I know : Defitition of an euler graph "An ...
2
votes
0answers
33 views

Number of “left-to-right” walks on a line graph

Let $G_n$ be the line graph on $n$ nodes. An example when $n=4$: Let $a_n(k)$ be the number of walks on this graph of length $k$, which start at node $1$ and end at node $n$. $a_n$ satisfies a ...
0
votes
1answer
18 views

What is the number of unique labeled connected graphs with N Vertices and K edges?

I've seen this question several times, and this one caught my attention. I'm now aware that there is no closed formula for this. My knowledge of graph theory is limited, and I wasn't able to find an ...
1
vote
0answers
13 views

Select a random edge [on hold]

Given a source of random bits and a multigraph G(V, E), provide an algorithm for selecting an edge e ∈ E uniformly at random in O(n) time.
4
votes
2answers
49 views

Question about triangle-free graphs

I'm asking for your help with this problem "Let $G$ be a triangle-free graph with $\delta > \frac{2n}{5}$. Show that $G$ is bipartite." Every book I read says it's obvious, but I can't see it ...
1
vote
2answers
30 views

Why the Ramsey number $R(2,4)$ is not equal to $2$?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. Here: I don't understand: For all $2$-colorings, it must have a $K_p$ and $K_q$ or it must have a $K_p$ or a $K_q$? I'm ...
3
votes
1answer
28 views

Show that if graphs are cospectral then they have the same odd girdth

Graphs are cospectral if they have the same set of eigenvalues together with their algebraic multiplicities. How can one show that graphs such as these have the same odd girth?
1
vote
1answer
18 views

Conting Homomorphisms from a cyle to another graph

There is a question that requires me to show that the number of Homomorphisms from a cycle of length n to a graph is the number of closed walks of length n in the second graph.
0
votes
0answers
6 views

tree symmetric across middle edge, all the way down

I came upon a tree which is symmetric across a middle edge in the sense that it is bicentral and removing the middle edge leaves two identical halves, and then the half in turn has the same "symmetric ...
2
votes
2answers
17 views

Graph Theory: A graph is acyclic then parent label is smaller than children label

I've come across the following theorem in a couple of books but can't quite find a formal proof of it. Theorem: A directed graph is acyclic, if and only if it is possible to assign numbers to each ...
6
votes
3answers
77 views

How to draw the 5 dimensional hypercube graph with 56 edge crossings?

I'm probably doing something stupid but I can't seem to think of a way to draw $Q_5$ with $cr(Q_5) = 56 $. In this paper the author says drawing a hypercube graph with $\leq56$ edge crossings is easy ...
0
votes
2answers
23 views

Why are the number of verticies in a clique graph less than its a parent graph [duplicate]

I am reading up about Graph theory and the example it gives for a Clique Subgraph looks like this... Now it states that the bottom graph is "obviously" the clique graph for the top. Is this because ...
1
vote
0answers
38 views

To find out the minimum required jumper number between objects

I try to find out the minimum required jumper number for connection between objects. The rule is : all objects are on a plane and need to connect all objects with only one connection. The minimum ...
4
votes
1answer
31 views

$\alpha$-critical graphs and chordless odd cycles

An $\alpha$-critical graph is a graph in which the removal of any edge increases the independence number. Sometimes isolated vertices are forbidden, but that is irrelevant for this question. It is ...
1
vote
1answer
34 views

Raising an adjacency matrix to a power: Why does it work?

An adjacency matrix $M$ represents the number of ways to travel between pairs of points in a network in exactly one move. $M^k$ represents the number of ways to travel between pairs of points in a ...
1
vote
0answers
104 views

$k$ Dimensional Weisfeiler-Lehman Method

I am reading An Optimal Lower Bound on the Number of Variables for Graph Identification (1992) On page 4 , the paper says, The second hope was partly based on the following result of Cameron ...
-1
votes
0answers
15 views

What is the average pathlength to cross any given graph? [closed]

@ Jedediyah In the answer to the question "... What is the average path length and probability to cross any given graph?...", you have answered that "...Let N be the matrix M with the last row and ...
0
votes
0answers
43 views

Worst case for the stable marriage problem

What is the worst case for the stable marriage problem? I know the worst case is $n^2 - 2n + 2$ but I would like to know how to prove it.
1
vote
2answers
27 views

Graph construction terminology

Given graph $G=(V,E)$, is there a graph $H=(U,F)$ where the edges of $H$ are the vertices of $G$ and the vertices of $H$ are the edges of $G$? If $G$ is a complete graph, what is $H$? How do cycles ...
-1
votes
2answers
38 views

Graph with a pendant vertex

I am trying to prove the following statement but cannot make a first step forward. If $G$ is a simple graph in which neighbours of an arbitrarily chosen vertex have different degrees, then $G$ has ...
1
vote
0answers
25 views

Independence of Events in Lovasz Local Lemma

Let $G$ be a (finite) graph with maximum degree $d$ and vertices $v_{1}, \dotsc ,v_{n}$. Let us associate an event $A_i$ with $v_i (i = 1, . . . , n)$ and suppose that $A_i$ is independent of the ...
0
votes
0answers
18 views

Upper limit on Ramsey number $R(a,b)$

How could we prove that if $R(a-1,b)$ and $R(a,b-1)$ are both even then $R(a,b)$ is strictly less than $R(a-1,b)+R(a,b-1)$ or $\begin{equation} R(a,b) < R(a-1,b)+R(a,b-1) \end{equation}$
0
votes
1answer
35 views

Graphing social connections in a middle school.

Imagine a middle school with the usual assortment of bullies and bullied, popular and lonely, violent and passive, and troubled. I try to keep up on who's doing well and who is not. My data consists ...
0
votes
0answers
16 views

Using graph theory in Wireless sensor network

I am doing my research in wireless sensor network. However, I am very much interested in graph theory too. I am asking this because I cant think any better source than here to answer this. The ...
0
votes
4answers
60 views

Is it possible to find the criminal with graph-theoretic methods?

I've been presented to a problem: Someone commited a crime. When interrogated, the people, named $G,m,M,J,D$ argued: $G:$ It wasn't $D$; It was $M$. $m:$ It wasn't $M$; It wasn't $D$ ...
1
vote
1answer
20 views

Meaning of 3-disjoint

Definition: Two edges $\{x, y\}$ and $\{w, z\}$ of $G$ are said to be 3-disjoint if the induced subgraph of $G$ on $\{x, y, w, z\}$ consists of exactly two disjoint edges. (See page 5 of this file.) ...
3
votes
2answers
32 views

Ergodic components of Markov chain by transition matrix

I would like to find an algorithm for obtaining all ergodic components of a finite Markov chain with discrete time defined by its transition matrix (i.e. ergodic subchains into which the given chain ...
1
vote
1answer
44 views

Edge colorability of small d/k graphs - among the largest known graphs for the undirected degree diameter problem

What is known about the edge colorability of the graphs residing in the small $d/k$ section in this table (upper left corner) ? For example, what is the chromatic index of the $d=4$, $k=4$ graph with ...
-1
votes
1answer
35 views

Trivial Graph theory questions [closed]

Can every disconnected graph be decomposed into 2 disjoint subgraphs ? If yes then edge-disjoint or vertex-disjoint ? and Why ? If not then what are the exceptions ? Given n vertices is it always ...
2
votes
1answer
76 views

Does an Eulerian semi-graceful polyhedral graph exist?

In a graceful graph, the vertices have number values that range from 0 to $n$ and $n$ edges with all values from 1 to $n$ that are differences between the vertex values. Here's a graceful but boring ...
3
votes
1answer
49 views

graph partition, second smallest eigenvalue.

In spectral graph partition theory, the eigenvector corresponding to the second smallest eigenvalue of the laplacian matrix of a graph, in general, is used to partition the graph. What is the ...
0
votes
0answers
25 views

Conjecture on different type of triangle in a complete graph?

How many different triangles are there in $K_5$? The Answer is 35.(The Moscow Mathematics Puzzle) Then I asked what about $K_6$, $K_7$ and so on ...? With my intuition I arrived at this ...
0
votes
4answers
38 views

If $G$ is a simple, connected graph with no loops or cycles, then it has at least two vertices with degree 1.

Question: Prove the statement: If $G$ is a connected graph with no cycles, then it has at least two vertices with degree 1. This seems pretty obvious, as if the graph has no cycles then it ...
0
votes
2answers
23 views

Finding isomorphism classes of graphs, given $|V|, |E|$, degree sequence, etc.

In this particular question I'm asked to find all the isomorphism classes of simple graphs, without loops whose degree sequence is: $3,3,2,2,2$, and to prove the ones I found are all the ones that ...