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

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
36 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
144 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
532 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
109 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
117 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
154 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
195 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
80 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
106 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
139 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
43 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 ...
4
votes
1answer
137 views

Graph presentation of Lexicographic shifts

Consider a finite alphabet $\{0,1, \ldots, n-1\}$. Let $\Sigma_n = \mathop{\prod}\limits_{j=1}^{\infty}\{0, \ldots n-1\}$ be the set of infinite one sided sequences and $\prec$ the lexicographic ...
2
votes
2answers
161 views

Degree Sequence Problem on $k$-Partite Graphs

The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees ...
0
votes
0answers
29 views

“Mutant knots” generalizable to “mutant tangled graphs”?

Just in case: Take a link L (drawn into the plane with over- and undercrossings), draw a closed loop C on it which cuts L in four points, rotate the inside of C around 180° (align the cut points on ...
5
votes
0answers
83 views

Implementations of Tutte polynomial [reference request, of a kind]

This question is not a 100% fit for MO, but it is a serious question that can be viewed as a sort of reference request, and I think fits here more than elsewhere. I have been asked to write a chapter ...
3
votes
1answer
339 views

Is there a graph with 99 vertices in which every edge belong to a unique triangle and every nonedge to a unique quadrilateral?

99-Graph:Is there a graph with 99 vertices in which every edge(i.e. pair of joined vertices) belong to a unique triangle and every nonedge(pair of unjoined vertices) to a unique quadrilateral?
2
votes
1answer
56 views

Graph construction to double coloring & Hadwiger number

For any graph $G$ let $\eta(G)$ be the Hadwiger number of $G$. Is there for every graph $G$ a graph $2G$ such that -- $\chi(2G) = 2\chi(G)$, and -- $\eta(2G) = 2\eta(G)$? For each one of the above ...
0
votes
1answer
70 views

Additivity of genus of a graph [duplicate]

Let $G$ be a finite simple undirected graph. Suppose there exist subgraph $G_1,G_2,\dots,G_n$ of $G$, such that $E(G_i)\cap E(G_j) = \emptyset$ and $|V(G_i)\cap V(G_j)| \leq 2$, for $i\neq j$. Then, ...
0
votes
0answers
154 views

Induced graphs of cayley graph

I have a Cayley graph $Cay(G,S)$, its group presentation $G=< S | R >$ and it is a metric graph by assigning a length equal to 1 to each edge. I also have an induced subgraph of that Cayley ...
1
vote
0answers
64 views

Recovering Spherical Harmonics from Discrete Samples

Consider a collection of $N$ points on the 2-sphere chosen uniformly at random. Let's say that there's an edge between two such vertices if their geodesic distance is less than $r_N$. The resulting ...
3
votes
2answers
193 views

Definition of the Moebius Ladder Graph

I found two different definitions of the Moebius Ladder Graph, whose essential difference is, whether the smallest one shall be $K_4$ or $K_{3,3}$. according to Wikipedia ...
0
votes
0answers
52 views

Preferential Attachment and salton similarity in directed networks

Preferential Attachment similarity between two nodes in an undirected graph is the degree of the first node multiplied by the degree of the second node. But what about directed graphs? Which degree ...
1
vote
1answer
81 views

Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language: $L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$. ($G$ ...
2
votes
2answers
132 views

Which graphs generate a matroidal independence complex?

The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$. Now, if $G$ is a well-covered graph (where all maximal ...
0
votes
0answers
43 views

Almost symmetric route in digraphs

Let $D=(V,E)$ be a digraph. A route of length $k$ in $D$ is a pair $L=(S,\sigma)$, where $S=(s_1,s_2,\dots,s_{k+1})$ is a sequence of $k+1$ elements of $V$, and ...