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
votes
1answer
8 views

Graph software for representing nodes and functional relationships between them

This may not be the best venue for this question, but I did not find an anatomy or medicine SE community, so I think mathematics (in particular, operations research) may be best. I briefly considered ...
1
vote
1answer
35 views

Sweet Graph Theory Problem

Here is a nice graph theory question for you all: Suppose we have the complete graph K(n). We then label each edge on this graph with either a 1 or a 0. A path is "sweet" if we are able to start at a ...
0
votes
0answers
11 views

Non-existence of commutative rings with many nilpotent elements with some restrictions where matrix powers are efficient

Cross-posted from MO. At the moment can't find better reference than "Cycle Enumeration using Nilpotent Adjacency Matrices with Algorithm Runtime Comparisons" though certainly there are others. ...
0
votes
2answers
21 views

Ambiguity regarding the definition of 'path' in graph theory

While going through the Introductory chapter of 'Graph Theory' by Bondy and Murty, I came across the definition of 'path' that says it's a sequence of vertices in such a way that two vertices are ...
3
votes
0answers
34 views

Number of players with most wins in tournament

$n\geq 2$ tennis players play each other once, and there are no draws. For which $1\leq k\leq n$ is it possible that exactly $k$ players have the (joint) highest number of wins? For example, $k=1$ is ...
3
votes
1answer
30 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
12 views

Degree of a self-complementary graph with $4k+1$ vertices [on hold]

How can we prove that every self-complementary graph on $4k+1$ vertices has a vertex of degree $2k$ ?
1
vote
1answer
16 views

Definition/Clarification of Graph Embeddings

Recently I started reading about graph embeddings, but I am unable to grasp its definition from Wikipedia. Can anyone explain this term with an example.
-3
votes
0answers
37 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. ...
4
votes
0answers
15 views

Graphs from which their minimal 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
13 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
28 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
14 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
20 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
45 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
34 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
14 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
50 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 ...
2
votes
1answer
30 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?
0
votes
2answers
24 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
78 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
116 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
33 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 ...