Tagged Questions

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...

learn more… | top users | synonyms

1
vote
1answer
99 views

How to model a time-discrete heat equation on a graph?

I would like to know how one can set up a time-discrete model for the heat equation on a graph? Is this problem using the heat kernel equation on a graph?
0
votes
0answers
72 views

Heat equation with graph laplacian

I would like to start with considering the time-dependent heat equation on a connected graph and consider its Laplacian matrix. Suppose we have a connected graph with unknown temperature on vertices. ...
0
votes
0answers
72 views

Eigenvalues of the Cayley-like graph

Let $ F_q $ be a finite field of characteristic 2. Let $ x^2 + Sx +P \in F_q[x] $ be an irreducible polynomial over $ F_q $, and let $ g $ be one of its roots in $ F_{q^2} $. Define a map $ M: ...
34
votes
6answers
3k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
13
votes
1answer
610 views

Who first dubbed them “expander graphs”?

Expander graphs ("sparse graphs that have strong connectivity properties") burst onto the mathematical scene around the millennium, but I have not been successful in tracing the origin of (a) the ...
7
votes
2answers
132 views

Bounds on chromatic number of $k$-planar graphs

A $1$-planar graph can be drawn in the plane so that each arc is crossed at most once by another arc. A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times. Planar graphs are ...
19
votes
0answers
673 views

Non-linear expanders?

Recall that a family of graphs (indexed by an infinite set, such as the primes, say) is called an expander family if there is a $\delta>0$ such that, on every graph in the family, the discrete ...
5
votes
1answer
159 views

Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small. The famous Nash-Williams conjecture claims ...
4
votes
2answers
248 views

Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...
0
votes
1answer
55 views

mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations. Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...
8
votes
5answers
1k views

Are all almost regular graphs obvious?

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively. A graph is almost regular if $\Delta-\delta=1$. Now, here is a simple way to generate ...
0
votes
0answers
28 views

number of bipolar orientations to acyclic ones

Given a $k$-regular graph $G$, is there an upper bound on the number of bipolar orientations that $G$ has? I am trying to show that the number of bipolar orientations is much much lower than the ...
5
votes
0answers
100 views

Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...
5
votes
0answers
152 views

Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?

Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then ...
2
votes
3answers
160 views

Examples of graph properties characterized by forbidden (not necessarily induced) subgraphs

A graph property is hereditary if it is closed under taking induced subgraphs (equivalently, if it is closed under removing vertices). A graph property is monotone if it is closed under taking ...
0
votes
0answers
37 views

Cycle cover of a cubic polyhedral graph

Tutte graph is a counterexample for the Tait's conjecture stating that all cubic graphs are Hamiltonian. For the non-hamiltonian graphs - is it true that all vertices of any such graph can be covered ...
2
votes
0answers
48 views

Regular graphs with unimodal subdegrees that are not distance-regular

Distance regular graphs are known to exhibit the following property: starting from an arbitrary vertex $\alpha$, let $k_i$ denote the number of vertices at distance $i$ from $\alpha$ (in terms of ...
1
vote
0answers
66 views

labeling vertices in a graph to minimize distance between adjacent vertices

We have a regular graph $G$ of degree $m$ on $n$ vertices and we label each of its vertices with the number $1$ through $n$. What can we say about the maximum difference between the numbers of two ...
7
votes
2answers
270 views

Wait time to grid network disconnection with failing edges

Let $G_n$ be an $n \times n$ planar toroidal grid graph, with each node connected to its four neighbors, with the top row connected to the bottom, and the right column connected to the left. Suppose ...
2
votes
0answers
60 views

Characterize the equivalence class of bipartite graphs obtained from each other by elementary row operations on their adjacency matrices

Let $M$ be an $m\times n$ matrix real matrix. Let $G$ be a bipartite graph, with partitions $A$ and $B$, such that $|A|=m$ and $|B|=n$. A node $i\in A$ is linked to a node $j\in B$ if and only if ...
7
votes
1answer
356 views

Paths in groups

Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$. Question: For what groups does there exist a Hamiltonian ...
1
vote
1answer
125 views

Sequences that represent different drawing of chords?

In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties. Actually my question is ...
0
votes
0answers
92 views

Has this type of Cayley graphs been studied before?

Let $\mathbb F_q $ be a finite field of characteristic 2. Let $ x^2 + Sx +P \in \mathbb F_q[x] $ be an irreducible polynomial over $ \mathbb F_q $. Let $$ T = \{ \left( \begin{matrix} ...
17
votes
0answers
155 views

A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph? I'd like to avoid exhaustive ...
4
votes
3answers
146 views

Is there any partition of a regular graph which in any part there exists a vertex with all its neighborhood?

Let we have a regular graph. I want to know if we can partition the vertex set of this graph while in any part there exist a vertex with all its neighborhood?
10
votes
1answer
269 views

doubly-stochastic isomorphisms of graphs

A doubly stochastic matrix that commutes with the adjacency matrix of a graph is a doubly-stochastic automorphism of that graph (definition by Tinhofer 1986). Each (classical) automorphism of a graph ...
2
votes
1answer
78 views

a necessary condition for a nonempty graph being a line graph

Every gragh below will refer to a finite simple graph. There is a necessary and sufficient condition for a nonempty gragh being a line gragh: Krausz's Theorem A nonempty gragh is a line gragh if ...
1
vote
0answers
114 views

Relationship betwen eigenvectors

Suppose that we have two matrices A and B. Matrix B is taken from A with one row and one column deleted. On the other hand A is n*n matrix and B is (n-1)*(n-1) matrix and is created by deleting last ...
1
vote
1answer
111 views

Cycles in directed graphs

Let G be a finite directed graph (allowing multiple edges). We define a cycle (as usual) to be a sequence of edges $e_0, e_1, \dots, e_{n-1}$ (up to cyclic permutation) such that the terminal vertex ...
10
votes
1answer
535 views

Where can I find Gonthier's Coq code proving the four color theorem?

In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq: Gonthier, Georges. Formal proof—the four-color theorem. Notices Amer. ...
6
votes
2answers
110 views

How to efficiently find a Hamiltonian cycle in a graph whose closure is complete?

A graph whose closure is the complete graph is Hamiltonian by the Bondy-Chvátal theorem, but I haven't found a polynomial algorithm for finding a Hamiltonian cycle in such a graph. Is there one that ...
0
votes
0answers
125 views

Basis of periodic tiling of Wang tile

Given a set of Wang tile, Given 3 periodic tiling: A, B, C We define 3 vector F[A], F[B], F[C] each vector correspond to the appearing frequency of each type of tiles in the tiling. Now, we ...
1
vote
1answer
90 views

simple cycle analog in 2D (with application in tiling)

We know that any closed cycle of a graph could be decomposed into sum of simple cycles. To translate this theorem into tiling of 1D (Wang tile). We know that any 1D periodic tiling could be ...
3
votes
1answer
118 views

Cayley graph which is isomorphic to the line graph of a complete graph

From the literature, we know that the line graph of a complete graph $L(K_{q})$ is a Cayley graph if and only if $q \equiv 3$( mod 4) is a prime power. Now, if $q \equiv 3$( mod 4) is a prime power, ...
-4
votes
2answers
82 views

About planar graphs? [closed]

Can any non-planar graph with n minimum crossing points be 'drawn' on a sphere so the vertice and edge sets are the same and it has a connected subset A with minimum r crossing points and a disjoint ...
1
vote
0answers
104 views

Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution. However, is there a well established counter-part ...
1
vote
0answers
84 views

What is the projective dual of a planar graph?

Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...
3
votes
0answers
56 views

Maximal $k$-chordal subgraph

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges ...
1
vote
1answer
94 views

How to calculate the maximum number of rainbows for arbitrary graphs?

This question is inspired by problem 1 of the combinatorics test of the 2012 third round iranian olympiad which is as follows: We've colored edges of $K_n$ with $n-1$ colors. We call a vertex rainbow ...
3
votes
2answers
179 views

Distance between two networks

Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) ...
3
votes
0answers
79 views

Reconstructing a function from its variants that negate one argument

Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ...
6
votes
1answer
155 views

Integral straight-line embeddings of planar graphs

Wikipedia says (in the article on Fáry's theorem), "Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...
4
votes
1answer
196 views

Extremal graph theory for directed graphs

In extremal graph theory, there are results such as $$t(C_4,G)\geq t(K_2,G)^4,$$ where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...
2
votes
1answer
81 views

Eigenvalues of a graph and its one-edge-delation graph

Let $G$ be any graph with at least one edge and let $e$ be any edge of $G$. Let $G-e$ denote the subgraph of $G$ obtained by deletion of the edge $e$. Assume that $G$ has $n$ vertices. Suppose ...
3
votes
1answer
110 views

A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not. The new problem is this. There is a tourist who has a having the following ...
0
votes
1answer
166 views

Spectral Graph Theory [closed]

Let G be an undirected graph, then Laplacian Matrix(L(G)) = Degree Matrix (D(G)) - Adjacency Matrix (A(G)). What is the relationship between laplacian and adjacency spectrum of undirected graphs?
0
votes
1answer
107 views

Laplacian matrix of a graph with negative weights

I am trying to calculate the Laplacian and Adjacency matrix of a graphs for positive and negative weights. If a graph be simple with only non-negative weight it is easier. But in my graph I have some ...
7
votes
4answers
312 views

Extremal examples for a folklore lemma on subgraphs of large minimum degree

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...
3
votes
0answers
140 views

Must distinct tree eigenvalues be relatively far apart?

How close to each other can two distinct eigenvalues of a tree be, as a function of the number $n$ of nodes ? For example, the path $P_n$ exhibits a gap of order $\frac{2\pi^2}{n^2}$ asymptotically ...
1
vote
0answers
44 views

Euclidean embedding of a graph based on 1-ring neighborhood distances only

Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...