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
2answers
38 views

Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...
0
votes
1answer
43 views

Probability of having no cycles of fixed length in $d$-regular graphs

According to this paper, the probability that a random $d$-regular graph of order $n$ has no cycles of length $c_1,c_2,\ldots,c_t$ is $$P=\exp\left(-\sum_{i=1}^t\mu_i+o(1)\right)$$ as ...
0
votes
0answers
19 views

graph reconstruction via canonical labeling [on hold]

Graph edge deleted reconstruction: Given an edge deleted deck find the canonical lexicographically ordered largest representation for each card. Find the card with largest canonical label this is the ...
7
votes
12answers
3k views

Graphs with fractal properties?

For the purposes of a research project, I am wondering if there are any resources on graphs with fractal properties, by which I mean self-similarity in particular. For instance, imagine a graph where ...
4
votes
1answer
114 views

Partitioning ${\cal P}([[1,n]])$

In an analysis of the Jacobi method for the computation of the spectrum of a Hermitian matrix, I face the following problem. Denote ${\cal P}_2(n)$ the set of doubletons $\{a,b\}$ in ...
3
votes
1answer
77 views

Method to construct a bipartite graph G' with 2n vertices from a graph G

I have seen mentioned in a talk an operation that takes a graph $G=(V,E)$ and constructs a new bipartite graph $G'=(V',E')$ such that $V' = V\times \{0,1\}$ and $E'=\{((i,1),(j,0)) : (i,j)\in E\} \cup ...
1
vote
0answers
42 views

Graph Theory for Dummies Book [migrated]

Does anyone have a good book on Graph Theory that will introduce me to some of the basic concepts without being so filled with terminology that it's hard to read? I have taken an introductory course ...
23
votes
5answers
21k views

How large is TREE(3)?

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman ...
5
votes
3answers
181 views

Generating (or availability of) large strongly regular graphs

Are there collections of already generated large strongly regular graphs available to download? By large I mean $n >= 200$ where $n$ is the number of vertices. I found Ted Spence's page on srgs, ...
9
votes
1answer
106 views

What are some useful invariants for distinguishing between random graph models?

Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as: The Erdos-Renyi model The Stochastic Block model The Watts-Strogatz model The Barabasi-Alber model ...
-3
votes
0answers
38 views

eigenvalues of cycle and its complement [on hold]

I am trying to find the eigenvalue of cycle graph and its complement. How to simplify.Suppose $\omega^{1}+\omega^{n-1}=2cos (2\pi/n) $, then, $\omega^{\frac{n-1}{2}}+\omega^{\frac{n+1}{2}}=?$ Is it ...
1
vote
1answer
53 views

approximate diameter of polytopes in high dimensions

I just came across the following problem: Let us consider the unit corner of the n-cube $$ \Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 ...
0
votes
1answer
84 views

Are constructive characterisations of k-regular (simple) graphs known?

By a constructive characterisation I mean a theorem giving a list of base graphs and a list of operations such that every graph in a given class is generated from the base graphs by applying some ...
2
votes
0answers
236 views

Partitioning graph for Graph Isomorphism [on hold]

Motivation: I am studying the graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases . Construction: $G$ is an $r$ regular graph, $k$ connected (not a ...
2
votes
1answer
53 views

Maximum and minimum diameter of categorical graph product

Let $G_i$ be connected finite simple undirected graphs with diameter $d_i$ for $i=1,2$. Assume that $G_1\times G_2$ is connected. (Here $G_1\times G_2$ denotes the categorical product.) In terms of ...
2
votes
0answers
22 views

Non-existence of commutative rings with many nilpotent elements with some restrictions where matrix powers are efficient

At the moment can't find better reference than "Cycle Enumeration using Nilpotent Adjacency Matrices with Algorithm Runtime Comparisons" though certainly there are others. Consider the following ...
12
votes
3answers
1k views

A question on representation of graphs

Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...
6
votes
1answer
466 views

Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$. Consider the bipartite ...
1
vote
0answers
173 views

“Graph Individualization”[ reference request] [closed]

Context: I am studying Weisfeiler Lehman method(WL method) and have clear idea about 1 and 2 dimensional WL method. I was wondering about the individualization process described below- ...
-2
votes
1answer
470 views

Conjugate vertices and distinguishing properties

Motivation (added) A finite $n$-set is uniquely described (up to isomorphism) by a single population number $n$. A finite $n$-set with $k$ predicates is uniquely described (up to isomorphism) by ...
1
vote
0answers
71 views

What characteristic of a graph depend on the vertex labeling?

Different labeling on a graph produces class of isomorphic graphs. Two isomorphic graphs possess similar characteristic such as connectivity, degree distribution of vertices, equality of spectrum and ...
-1
votes
0answers
30 views

Any polynomial-time algorithm for hypergraph bisection? [closed]

I work with hypergraph partitioning. I want to divide a complete weighted hypergraph into 2 parts using cut-net metric, a sum of all edges cut, and connectivity metric. Is there a polynomial-time ...
0
votes
1answer
211 views

Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$). The cost to send $x$ unit of flow through edge $e_i$ is defined ...
4
votes
0answers
73 views

“Edge Density” of Infinite Planar Graphs

Given an infinite planar graph $G$, let's denote by $\{H_1,H_2,\dots,H_m\}$ all the labeled graphs on $n$ vertices that appear as subgraphs of $G$. Also let $$d_n=\frac{\sum_{i=1}^m \#E(H_i)}{nm}$$ ...
2
votes
1answer
112 views

Embedding graphs into hyperbolic spaces

Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?) I don't ...
3
votes
3answers
154 views

Question about the balance of a signed graph construction

When I asked this question before I got nary a nibble. That means either the question was too weird to resonate with anyone out there, or I did not make it clear that there was a question there that ...
2
votes
1answer
135 views

inequality with exponents

We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v ...
3
votes
1answer
187 views

Can every permutation group be realized as the automorphism group of a graph (acting on a subset of the vertices)?

By Frucht's theorem, every finite group can be realized as the automorphism group of a finite undirected graph. Because a permutation group is a finite group, it is clear that every permutation group ...
9
votes
2answers
307 views

Is every metric space quasi-isometric to a graph?

I've proved that if $(X, d)$ is a geodesic metric space then there exists a graph which is quasi-isometric to $X$...during this proof I've precisely used the fact that given two point in $X$ there ...
20
votes
5answers
2k views

The Matrix-Tree Theorem without the matrix

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me ...
3
votes
0answers
88 views

Does this notion of “$\mathcal{F}$-digraph” appear in the literature?

By a digraph, I mean a quiver with no multiple edges. So in particular: Loops are okay. An infinite set of vertexes is okay. Furthermore, I will tend to identify each digraph with its underlying ...
0
votes
1answer
192 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
4
votes
2answers
163 views

irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...
1
vote
0answers
66 views

Efficient realization of a restricted neighborhood hypergraph

In a graph $G$, the (open) neighborhood of a vertex $v$ is the set of vertices adjacent to $v$ (so vertex $v$ is excluded). The neighborhood hypergraph of $G$, denoted by $\mathcal{N}(G)$, is a ...
1
vote
2answers
186 views

Hedetniemi's conjecture for graphs with countable chromatic number

Are there graphs $G, H$ such that $\chi(G) = \chi(H) = \aleph_0$, but $\chi(G\times H) < \aleph_0$?
11
votes
0answers
1k views

A new lower bound for the chromatic number of a graph?

Let $S_{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph $G$. Let $S_{-}(G)$ denote the sum of the squares of the negative eigenvalues and $q$ the ...
9
votes
0answers
137 views

What algebraic structures are related to the McGee graph?

Recall that an $(n,g)$-graph is a simple graph where each node has $n$ neighbors and the shortest cycle has length $g$, while an $(n,g)$-cage is $(n,g)$-graph with the minimum number of nodes. The ...
1
vote
2answers
120 views

Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties: The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it). $T$ has a ...
3
votes
1answer
162 views

Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...
3
votes
1answer
73 views

Good broad review of agent-based modeling? [closed]

Trying to find some good review of agent-based models and networks, specifically models that are defined by a graph of interacting nodes, that covers analysis of collective behavior based on model of ...
2
votes
2answers
131 views

Detecting HNN-Extension and free products with amalgamation

This question is partly connected with the following Connection between Stalling's end theorem and Seifert-van Kampen Theorem. By Stalling's Theorem a group with more than one end splits over a ...
3
votes
1answer
660 views

Rooks on a lifeline

The short version of this question is: If $G$ is a graph whose nodes are associated with squares of a chessboard, such that no two nodes in the same row or column of the board are adjacent, we ...
-1
votes
1answer
70 views

Categorical product of graphs and chromatic number

Let $(G_i)_{i\in I}$ denote a family of simple, undirected graphs (finite or infinite). Let $\prod_{i\in I}G_i$ denote their categorical product. Why do we have the inequality $$\chi(\prod_{i\in ...
7
votes
2answers
1k views

Eigenvectors and partitions of graphs

Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ ...
1
vote
0answers
80 views

3-regular (cubic) graph with adjacency eigenvalue 1

Suppose $A\in\{0,1\}^{n\times n}$ is the adjacency matrix of a 3-regular (cubic) graph $G=(V,E)$; that is, all $n$ vertices $v\in V$ in the graph have three neighbors. Is there a nice necessary ...
7
votes
1answer
1k views

Has anyone seen this graph?

I recently constructed the graph shown below in the process of investigating some problems regarding line graphs and homomorphisms, and then happened to see it on wikipedia. I was wondering if anyone ...
1
vote
1answer
199 views

Can we estimate the probability $\mathbf{P}(a-k|a - b) $ on a random graph?

Let $G=(V,E)$ be an undirected random graph such that $V$ is the set of nodes, and $E$ is the set of edges Assume the ground graph $G$ is sparse enough, for example, $\frac{|E|}{|V|}= c \in [10, ...
1
vote
0answers
74 views

Obtaining a quasi-isometry of the 'boundary'

It is well-known that a quasi-isometry induces a homeomorphism on the space of ends of say a locally finite graph for simplicity. Clearly the converse is not true. In other words the concept of ends ...
2
votes
1answer
99 views

Connection between Barnette conjecture and hardness of cubic graph decomposition

Motivated by this post on cubic graphs decompositions and the connection to Barnette's conjecture, I am interested in decomposing a connected bridgeless cubic graph into edge-disjoint paths of length ...
6
votes
1answer
357 views

How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs. A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...