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

13
votes
0answers
265 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
369 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
300 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
274 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
288 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
151 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
147 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
495 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
151 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
166 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
95 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
339 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
123 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
111 views

Applications of Cayley Graphs in Physics

I have been recently reading about Cayley graphs and character theory. It is evident that Cayley graphs are very useful tool in theoretical computer science. In physics, Cayley graphs seem do appear ...
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
330 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
122 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
200 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
130 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
179 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
194 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
32 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
72 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
95 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
78 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, ...
5
votes
0answers
70 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$. ...
5
votes
0answers
138 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
73 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
149 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
79 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
66 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
283 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
182 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
60 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
202 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
186 views

Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

Call this problem DBPP (for disjoint pair of bounded paths). There is a polynomial algorithm for finding a pair of edge disjoint paths with the minimum sum of weights ([Suurballe's algorithm] ...
5
votes
0answers
214 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
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
22 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
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 ...
4
votes
0answers
45 views

Can't understand why this doesn't satisfy Laman's theorem

Definition: http://en.wikipedia.org/wiki/Laman_graph The following graph (top of picture) has $12$ vertices and $2\cdot12-3 = 21$ edges. I've tested all $2^{12}$ subsets of vertices, and all ...
4
votes
0answers
80 views

Graph composed of matchings and K_4

Let $G′ = (V, E_1 \cup E_2 \cup E_3)$ be a graph, where $E_1$ and $E_2$ are (nonempty) matchings and $E_3$ is the set of edges of a nonempty collection of pairwise vertex disjoint copies of $K_4$. ...
4
votes
0answers
92 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being ...
4
votes
0answers
84 views

$f$-factors and fractional $f$-factors and odd cycles

For a graph $G=(V,E)$ and a nonnegative integer valued function $f$ defined on $V$, an $f$-factor of $G$ is a spanning subgraph $F\subseteq G$ such that $d_F(v)=f(v)$ for all $v\in V$. A fractional ...
4
votes
0answers
62 views

Embeddings of graphs on surfaces

I need your help in the next problem: I use $N_g$, $g \geq 1$, to denote the nonorientable surface which can be constructed by inserting $n$ cross-caps on the sphere (these cannot be embedded in ...
4
votes
0answers
180 views

What can be said about the number of connected components of $G(n,p)$ random graphs?

By a $G(n,p)$ graph we mean a graph on $n$ vertices, all possible edges are independently included randomly with probability $p$. What can be said about the number of connected components? For ...
4
votes
0answers
74 views

Sequences of Integers such that no one divides the product of two others.

I'm working on of a problem of Bollobas' Modern Graph Theory, but I can't seem to get the last part of the problem: Let $1<a_1<a_2< \cdots a_k \leq x$ be natural numbers. Suppose no $a_i$ ...
4
votes
0answers
350 views

What is a bridgeless undirected planar 3-regular bipartite graph?

Draks asked a question about a sentence in Wikipedia stating that such-and-such (NP-hardness of Hamiltonian path detection) is true for "bridgeless undirected planar 3-regular bipartite graphs". What ...
4
votes
0answers
33 views

dominating set: NP-hard on graphs without cycles of length 4 and shorter?

does anyone know whether the problem Dominating Set is still NP-hard on graphs without "triangles" and "rectangles", i.e., graphs without cycles of length 4 or 3? Thanks