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

19
votes
0answers
373 views

Is Erdős' lemma on intersection graphs a special case of Yoneda's lemma?

Under which name is the following proposition filed actually: Every poset $P$ embeds fully and faithfully in the powerset of $P$, ordered by subset inclusion. Let me call it Dedekind's lemma. ...
12
votes
0answers
389 views

Normalizers of automorphism groups

In abstract groups $\Gamma$ the normalizer $N_\Gamma(S)$ of a subset $S\subseteq\Gamma$ is the subgroup of all $x \in \Gamma$ that commute with $S$, i.e. $xS = Sx$, i.e. $x\ y\ x^{-1} \in S $ for all ...
10
votes
0answers
314 views

Analyzing a class of vertex-deletion games

As part of the discussion on this question (Permutation Game Redux), a simple vertex-deletion game was proposed. The game is very simple. Disconnect. Players alternately remove vertices from a ...
9
votes
0answers
331 views

Expected value of the distance square

Given two points $X,Y$ on two sides of square $[0,1]\times [0,1]$ ($X:(0,1/2),Y:(1,1/2)$ (PS: My original question is $X,Y$ on opposite of a square, but I think that's not the real case) )and $n$ ...
9
votes
0answers
328 views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
8
votes
0answers
167 views

Does this graph have a name?

Does graph shown below from the paper Dissection Graphs of Planar Point Sets by P. Erdos, L. Lovasz, A. Simmons, and E.G. Straus have a name? Does it come from a family of related graphs?
8
votes
0answers
159 views

Branching processes and couplings

A text I am reading is discussing ways to couple branching processes, and describes the following 2 pairings, the latter of which I am failing to understand. (I include the former for the sake of ...
8
votes
0answers
523 views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
8
votes
0answers
153 views

Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant ...
7
votes
0answers
167 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 ...
7
votes
0answers
97 views

A connection between nonplanar complete graphs and the alternating group?

I went to an undergrad's senior honors thesis presentation a few days ago. She was discussing crossing numbers and mentioned that complete graphs $K_n$ are nonplanar iff $n \geq 5$. ?Coincidentally? ...
7
votes
0answers
344 views

Problem with an algorithm to $3$-colour the edges of cubic graphs

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence ...
6
votes
0answers
124 views

Parity of sum of Kronecker deltas in a graph

For some fixed $n\in\mathbb N$ let $G$ be a graph on the vertex set $\{1,\dots,n\}$ with a total number of $k$ edges $e_1,\dots, e_k$. For any vertex colouring $c(i)$ of the graph, $\delta_e$ is ...
6
votes
0answers
83 views

Quickest way to solve a matrix one step at a time.

I have a $14\times14$ matrix with a possibility of six states in each position The matrix is random each time. An example matrix would be: $$ \begin{pmatrix} ...
6
votes
0answers
78 views

Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
6
votes
0answers
336 views

Slices of a hypercube

Take the unit $d$-cube with vertices $\{0,1\}^d$, and restrict to the vertices that lie between (or within one of) a pair of parallel hyperplanes. These vertices form a graph whose edges are the edges ...
6
votes
0answers
126 views

Combinatorial vs. geometric symmetries of graphs and their drawings

Associated with a graph $G$ and its automorphism group $\text{Aut}(G)$ (reflecting its combinatorial symmetries) are drawings in the plane with - eventually - one or more (geometric) symmetry groups. ...
6
votes
0answers
206 views

Probability of the existence of a path of a specified length between any tw0 vertices in a random graph

Let $G$ be a graph with $n$ vertices, whose average degree is $k$. What is the probability that between any two vertices, there exists a path of length at most $l$? NOTE: For the above problem the ...
6
votes
0answers
132 views

Unit Distance structure of Hoffman Singleton graph

This question has been bugging me since last 3 years. Prove or disprove that Hoffman Singleton is an unit distance graph in $\mathbb R^2$. For those who are new to unit distance graphs, A graph is ...
6
votes
0answers
180 views

What do we know about graph degree sequences?

The sequence of sizes of single vertex cuts of a graph is called its degree sequence. Is there an agreed-upon name for the sequence of sizes of k-vertex cuts? What can be said about two graphs which ...
6
votes
0answers
195 views

Determining graph minors quickly

I know very little graph theory. I am trying to determine if one graph, A, has as a minor another graph, B. I know the problem is slow in general, so I am looking for things that I might be able to ...
5
votes
0answers
43 views

How can a finite graph be viewed as a discrete analogue of a Riemann surface?

In the paper "Riemann–Roch and Abel–Jacobi theory on a finite graph" by Baker and Norine, the first line of the abstract states: "It is well known that a finite graph can be viewed, in many respects, ...
5
votes
0answers
83 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
5
votes
0answers
106 views

Have these (extremely simple) classes of algebraic structures been considered in the literature? If so, what are they called?

Questions. Have the following kinds algebraic structures been considered in the abstract algebra literature etc.? If so, what are they really called? (I have used made-up terminology for the sake ...
5
votes
0answers
44 views

What is the maximum number of edges in an $n$-vertex non-Hamiltonian graph of minimum degree at least $2$?

Q: What is the maximum number of edges in an $n$-vertex non-Hamiltonian (simple) graph of minimum degree at least $2$? This question relates to Maximum number of edges in a non-Hamiltonian graph ...
5
votes
0answers
37 views

How many hamilton paths can a non-hamiltonian graph have?

What is the maximum number of hamilton paths a graph with $n$ vertices can have without having a hamiton cycle ? If my turbo pascal program works well, the first few values for $3,4,...$ vertices ...
5
votes
0answers
100 views

Is there a name for graphs with the following property?

The property of the graph is the following: For any vertex, there is a hamiltonian path starting with this vertex, but the graph is not hamiltonian. The following graph is a small example: ...
5
votes
0answers
38 views

Name for Number of Ancestors/Descendants of Vertex in Directed Acyclic Graph

Let $G = (V, E)$ be a directed acyclic graph. For each vertex $v \in V$, define the ancestors of $v$ to be the set of vertices $u \in V$ such that there exists a directed path from $u$ to $v$. ...
5
votes
0answers
81 views

Probability of transmission between two nodes in a neural network at exactly d timesteps

I have a network which is an Erdős–Rényi graph. It is a simple neural network with degree 0.7N where N is the number of nodes. Each weight between neurons is 1/N, meaning that if node n has fired the ...
5
votes
0answers
129 views

Odd Town Problem.

QUESTION: A town with $n$ inhabitants has $m$ clubs such that each club has an odd number of members and any two different clubs have an even number of common members. Show that $m\leq n$. ...
5
votes
0answers
144 views

How is graph theory used to solve problems in number theory?

What are some applications of graph theory in number theory? How can a graph theory approach be useful to solving number theory problems? In general, is graph theory ever useful in making number ...
5
votes
0answers
82 views

Tilings of the Hyperbolic plane

Given a tiling of the hyperbolic plane projected onto a unit disc such as this which can be considered as a graph. I then define some functions: $f(r) =$ number of graph nodes contained within the a ...
5
votes
0answers
152 views

Get the adjacency matrix of the dual of a 3-connected $k$-regular $G$ without pen and paper

As advised on meta, I'll repost this question, which is close to this one, with the additional condition, that $G$ is 3-connected: Given the adjacency matrix $A$ of a $k$-regular planar ...
5
votes
0answers
81 views

Is Paley-13 graph a unit distance graph in 3D space?

The 13-node Paley graph has vertices 1 to 13 that are connected by an edge when their difference is one of the values $(1,3,4,9,10,12)$ Can this graph be put into 3D space so that all edges have ...
5
votes
0answers
67 views

Homomorphism for a fixed graph NP-complete?

Let $G$ be the following Graph: We want to decide whether for an input structure $\mathcal{S}$ there exists a homomorphism $S \to G$. We will call this problem $HOM_G$. The task at hand is to show ...
5
votes
0answers
290 views

Intersecting Odd Cycles, Chromatic Number, and the Subgraph $K_5$

Consider a graph $G$ such that every pair of odd cycles in G intersect. Then $\chi(G) \le 5$. Furthermore, $\chi(G) = 5$ implies $K_5 \subset G $. Here is the proof of the first claim: Let ...
5
votes
0answers
192 views

What is the probability that a random $n\times n$ bipartite graph has an isolated vertex?

By a random $n\times n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$. I want to find the ...
5
votes
0answers
61 views

Erdos Ko Rado for hypergraphs of bounded degree?

The Erdos-Ko-Rado theorem states that if $H$ is a $k$-uniform hypergraph on $[n]$ which is intersecting, then $|H| \leqslant \binom{n-1}{k-1}$. The easy example which shows this is tight is just take ...
5
votes
0answers
97 views

What is special about simplices, circles, paths and cubes?

There are some ubiquitous families of graphs — the complete graphs (or simplices) $K_n$, the circle graphs $C_n$, the path graphs $P_n$, and the hypercube graphs $Q_n$ — that intuitively ...
5
votes
0answers
468 views

Embedding Mazes - Spanning Trees of a Grid Graph

A perfect maze (a maze with a unique solution) can be seen as a tree, where each node corresponds to a cell in the maze, and where edges corresponds to passages (missing walls) between cells. Two ...
5
votes
0answers
207 views

“Semidirect product” of graphs?

The first subquestion is "has a standard notion of semidirect product been defined in graph theory"? If yes, i'd like to know if the definition i'm gonna give is equivalent to the standard one. I'd ...
5
votes
0answers
219 views

Can the 57-cell be made in vZome without strut crossings?

Here's the 57-cell in vZome with lots of strut crossings: Is it possible to construct the 57-cell in vZome without any strut crossings? That is, 57 nodes, 171 struts, in the 57-cell / Perkel graph ...
4
votes
0answers
40 views

Probabilistic counting inequality

I am reading a proof involving the existence of a property in a tournament (a directed complete graph). To make the proof work, we need to have $n^ke^{-n/2^k}<1$. Here $n$ is the order of the ...
4
votes
0answers
59 views

Can bipartite graphs have the following properties?

Let G be a bipartite graph with at least $3$ vertices. Can it have the following properties simultaneously ? $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no ...
4
votes
0answers
24 views

Is this the smallest graph with the desired properties?

The above graph has the following properties : $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no hamiltonian cycle. $3$) It has no cycle of length $3$. $4$) It is ...
4
votes
0answers
41 views

Who has a winning strategy in the hamilton-circle-game?

The game starts with a graph with $n$ vertices and no edges. The players alternately add edges until the graph contains a hamilton-circle. The player who made the last move loses. Who has a winning ...
4
votes
0answers
47 views

How many distinct chromatic polynomials are there for simple connected graphs?

For a given order $n$, the number of graphs that are determined uniquely by their chromatic polynomial is A137568. This sequence starting with n=1 is: ...
4
votes
0answers
24 views

Largest Matching whose removal does not leave Eulerian components

Task: Given an undirected graph $G = (V, E)$, find a largest matching $M \subseteq E$ such that $G-M$ has no Eulerian components (i.e. all connected components of $G-M$ must have odd-degree ...
4
votes
0answers
75 views

A game on a smaller graph

In this question Alice and Bob play a game on $K_{2014}$, Alice directing one edge, Bob directing $1$ to $1000$ edges with Alice trying to make a cycle. The proof that Alice can win depended on the ...
4
votes
0answers
67 views

Is every minor-closed class of graphs that excludes some $S_n$ or $P_n$ of bounded tree-width or clique-width?

Does every minor-closed class of graphs that excludes some $S_n$ or $P_n$ have (one or more of) bounded tree-width or bounded clique-width? By $S_n$ I mean a star with $n$ leaves and by $P_n$ I mean ...