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
7 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
1answer
21 views

Adjacency table, directed graph

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 ...
0
votes
1answer
22 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
17 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
16 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
41 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
29 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
48 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
26 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
17 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
16 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
70 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
92 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
12 views

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

@ 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
24 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
19 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
30 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
43 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
33 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
75 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 ...
1
vote
1answer
17 views

Given $G_n$, a graph with $2^n$ vertices, show $G_4\simeq Q_4$.

Let $G_n$ denote the $2^n$ vertices graph in which every vertex is labeled with a string of $n$ bits. A pair of vertices are adjacent if and only if their bit strings differ in exactly 3 digits. ...
2
votes
1answer
31 views

The upwardly closed subgraph

I'm reading the book Probabilistic Graphical Models (Koller and Friedamn). I'm not quite sure about this example: Given the next graph: The updwardly closed subgraph K+[C] is: I don't get it. I ...
0
votes
0answers
16 views

Existence of an $x,U$-fan in a $k$-connected graph

Let $G$ be a $k$-connected graph. An $x,U$-fan is a set $U\subseteq V(G)$ of size $|U|\ge k$ together with a vertex $x\in V(G)\backslash U$ and a set of disjoint $x,U$-paths whose only common vertex ...
1
vote
1answer
29 views

Construct a digraph which reflect four given rankings and use component analysis to interpret these rankings

Suppose that four judges $J_1$, $J_2$, $J_3$, and $J_4$ each rank eight objects: $O_1,O_2,\ldots,O_8$ independently. Their rankings are $$\begin{array}{cc} J_1: & O_1\ O_2\ O_3\ O_4\ O_5\ ...
2
votes
1answer
43 views

Find edge disjoint spanning tree subgraph between A and B

Given an undirected graph G(V,E). A and B are elements of V. Identify a subgraph of G containing A & B with 2 edge disjoint spanning trees (or prove one doesn't exist). I have found several ...
4
votes
0answers
52 views
+50

Bounding 2nd-smallest eigenvalue of the Laplacian of the binary tree

I am reading on my own the notes of this lecture series from 2012: http://www.cs.yale.edu/homes/spielman/561/2012/lect04-12.pdf. In section 4.7.2 (page 8) it's mentioned that we can prove a lower ...
2
votes
1answer
26 views

Can CNF Hamiltonian graphs be turned to “DNF” graphs?

Given a CNF SAT formula, we can turn it into a Hamiltonian graph, which is Hamiltonian iff the formula is satisfiable. Now, we can transform the CNF formula into a DNF one. My question is, can the ...
0
votes
1answer
26 views

Optimal partitioning of a planar graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
-1
votes
0answers
20 views

cycle decomposition of graphs

I am trying to find the number of elements in cycle space of a graph G,as I know every even graph has a cycle decomposition,and I wana find the number of cycles in a graph and I think the cardinality ...