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

3
votes
2answers
14 views

What is the graph that corresponds to $Q'_8$ generalized quadrangle ? Could you please explain this in plain english?

In this paper a table about large graphs with given degree and diameter graphs is shown: I would like to know what the adjacency list of the graph denoted by: in the table above is. Could ...
-1
votes
1answer
18 views

A cut in directed graph

Let $(S,T)$ be a cut in a graph $G$. What is the cut set? Is it the set of all edges from $S$ to $T$ or does it include the edges from $T$ to $S$?
-1
votes
0answers
27 views

corllary of tutte's theorem [duplicate]

I have read the proof of "prove that a graph $G$ contains $k$ independent edges iff $q(G−S) \le |S|+|G|−2k$" and I am just confused at one place how after adding $n-2k$ universal vertex $G'$ follows ...
1
vote
1answer
35 views

Iverson Brackets

I would appreciate some feedback on my notation. I'm using Iverson brackets, which I'm sort of new to as a concept, but it seems simple enough. The degree of a vertex $v_n$ is given by the sum of the ...
0
votes
0answers
9 views

Question regarding isomorphisms formed by deleting various edges in a plane triangulation…

Consider a plane triangulation $T$ with $m$ edges numbered $1, 2, … , m$. Form the near-triangulation $G_k$ by deleting the edge $e_k$ in $T$. Suppose the $m$ near-triangulations $G_k$ for $k = 1, 2, ...
2
votes
1answer
32 views

Must the number of people at a party who do not know an odd number of other people be even

I have a homework question in my discrete mathematics class as the title shows, I feel the answer is no, but googling this question seem's to contradict my answer. Let me explain: So if they are ...
0
votes
0answers
21 views

sub-series matching, graph matching

Let $A={a_{1}...,a_{N}}$ and $B={b_{1},...,b_{M}}$ be finite sets, such that N >= M. find a mutually-exclusive covering of size M: $A_{1},...,A_{M}⊂A$ that is monotonic, meaning: if $a_{i} \in A_{l}$ ...
1
vote
0answers
19 views

Obtain cycles with $a < $ nr. of edges $< b$

I have a chemistry/mathematical problem and I would like to get your opinion. Imagine you are generating a planar, cyclic molecule, with a total $N$ is the number of atoms. By Euler graph theory, the ...
7
votes
1answer
107 views

Extremely difficult graph theory question

The following question was on my introduction to combinatorics and graph theory exam. I asked around and it seems no one managed to solve it. I certainly didn't, even now after thinking about it for a ...
1
vote
2answers
17 views

eigenvalues of cycle graph and its complement graph

I am trying to find the eigenvalue of cycle graph and its complement. How to simplify.Suppose $\omega^{1}+\omega^{n-1}=2cos (2\pi/n) $, then, $\omega^{\frac{n-1}{2}}+\omega^{\frac{n+1}{2}}=?$ Is it ...
-2
votes
1answer
20 views

Graph software for representing nodes and functional relationships between them [on hold]

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 ...
0
votes
0answers
16 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
26 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
37 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
41 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
14 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
17 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
21 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
14 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
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 ...
-1
votes
1answer
33 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
1answer
15 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
36 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
46 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
35 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
19 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
51 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
32 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
32 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
25 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
81 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
132 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}$