Questions tagged [graph-theory]
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, topological-graph-theory, random-graphs, graph-colorings and several others.
5,150
questions
2
votes
1
answer
62
views
A simple equality for book embedding of two graphs
A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is ...
1
vote
2
answers
270
views
Is a graph with edges between edges and nodes still a graph? [closed]
I am interested in how a structure of the following representation would be called or if there even is an established definition of such a thing.
The structure is similar to a graph. The ...
2
votes
0
answers
214
views
Graphs with the same Laplacian eigenvalues
Let $L$ be the
Laplacian matrix
for a simple graph $G$ of $n$ vertices,
and $\lambda_0,\ldots,\lambda_{n-1}$ its $n$ eigenvalues.
Q.
What is the cardinality of the class of $n$-vertex graphs $\...
2
votes
1
answer
41
views
Simple balance incomplete block design, (complete graph clique decomposition)
I am trying to find methods to construct a $(n,k,1)$-BIBD with large $n$ and $k$.
Basically, I'm wondering if there's an established method to create as many sets of size $k$ from elements $\{1, ..., ...
0
votes
0
answers
346
views
crossing number and thickness of a simple graph $G$
Crossing number$($cr$)$: The crossing number of a simple graph is the minimum number of crossings that can occur when this graph is drawn in the plane where no three arcs representing edges are ...
8
votes
3
answers
7k
views
When is the independence number of a graph equal to its clique cover number?
Let G be a connected graph without loops.
The (vertex) independence number is the maximum size of a set of vertices such that no two vertices in the set are connected by an edge.
The (vertex) clique ...
6
votes
2
answers
235
views
Lovasz local lemma for the edge model
In order to successfully apply the Lovasz local lemma, one needs the events to be relatively independent. This (sometimes) works well in the $G(n,p)$ model of random graphs, where the presence or ...
1
vote
1
answer
242
views
Finding good flows to upper bound effective resistance
Thomson's principle for electrical networks states that if $G$ is a network (a weighted graph), $a$, $b$ are vertices of $G$, then the effective resistance between vertices $a$ and $b$ in $G$ is given ...
4
votes
0
answers
225
views
How many arrangements of $n$ points with $k$ edge lengths exist in $d$ dimensions?
[Asking on behalf of a high school mathematics course, but responses written at any level are welcome!]
I was recently reading over a nice puzzle called the four points, two distances problem:
...
1
vote
2
answers
505
views
Determine number of possible paths in an undirected graph [closed]
I have a graph consisting of a start point $S$, a finish point $F$ and a number of intermediate points $P_i$. The points are connected by a set of edges, as shown in the graph below. I need to ...
2
votes
2
answers
294
views
Random walk and isoperimetric constant
I assume that a result of the following kind is known, and I would really appreciate a reference for it... Or at least, some hints as to where to start looking.
Theorem(?): Let $\varepsilon>0$ ...
2
votes
2
answers
226
views
Adjacency matrix of total graph
Is there a nice way of relating the adjacency, incidence , Laplacian matrices and other matrices associated to a graph of a total graph with its original graph, or, say, at least relating that of the ...
1
vote
0
answers
160
views
Large bounded degree expanders in the hypercube
Does the $n$ dimensional hypercube graph contain large bounded degree expanders as subgraphs? For example, of exponential size in $n$?
If not, one could relax the problem and allow the maximum ...
0
votes
0
answers
157
views
Paths in graphs as a vector space or matroid
If I have a simple graph $G$, and what to count the number of simple paths between two distinct vertices, can the paths be seen as independent sets of a vector space, or even somehow, a matroid? I ...
3
votes
1
answer
138
views
Eigenfunctions adjacency operator on infinite graph in $l^2$
Let $\Gamma$ be an infinite (connected) graph without edges going from a vertex to itself (though it might have multi-edges). Let us suppose that $\Gamma$ has finite valence.
Is there always a ...
0
votes
1
answer
319
views
Graphs with circulant distance matrices
The cycle has this property. For instance, the distance matrix for a 6-cycle is:
$A=\begin{bmatrix}
0 & 1 & 2 & 3 & 2 & 1 \\\\
1 & 0 & 1 &...
5
votes
1
answer
269
views
Combinatorial Skeleton of a Riemannian manifold
In Chung and Yau's paper: "A combinatorial trace formula" (MSN), they proved
a combinatorial version of Selberg's trace formula for lattice graphs.
I learned also in the setup that it makes sense to ...
1
vote
1
answer
129
views
Representation-finite implies planar for quiver algebras?
Let $A=KQ/I$ be a finite dimensional quiver algebra with an admissible ideal $I$.
Is it true that in case $A$ is representation-finite, $Q$ has to be planar?
In case it is true a possible approach ...
0
votes
0
answers
58
views
Decomposition of triangle-free bridgeless planar cubic graphs
Question:
is it true that every triangle-free connected bridgeless planar cubic graph can be decomposed into a vertex-disjoint cycle cover and a single maximal matching of the edges that are adjacent ...
31
votes
0
answers
893
views
Is this representation of Go (game) irreducible?
This post is freely inspired by the basic rules of Go (game), usually played on a $19 \times 19$ grid graph.
Consider the $\mathbb{Z}^2$ grid. We can assign to each vertex a state "black" ($b$), "...
0
votes
1
answer
91
views
Recognition of a graph as a product of its quotients
Is there an algorithm to determine whether a given simple graph $G$ is a product graph, typically, say a cartesian product graph of two smaller simple graphs $G_1, G_2$, such that the two simple ...
7
votes
1
answer
208
views
Embeddability of all graphs of cardinality $\kappa$ into one graph of cardinality $\kappa$
Does every infinite cardinal $\kappa$ have the following property?
There is a simple, undirected graph $G_0=(\kappa, E_0)$ such that every simple, undirected graph $G=(\kappa, E)$ is isomorphic to ...
5
votes
0
answers
93
views
Increasing the Hadwiger number by identifying non-adjacent points
This is a specialization of a more general, still unanswered question.
Suppose $G$ is a finite, simple graph. Let $h(G)$ denote the Hadwiger number, that is, the maximum $n\in\mathbb{N}$ such that $...
4
votes
1
answer
241
views
Probability of a vertex being a "degree-celebrity" in a random graph
If $G(n,p)$ is a random graph of the Erdös-Rényi model,
what is the probability that $\mathrm{deg}(v)\gt\mathrm{deg}(u)\ \forall u\in\mathrm{adj}(v)$
Please feel free to relate answers to other ...
1
vote
0
answers
43
views
Coloration of an interval graph with constraints [closed]
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
18
votes
1
answer
4k
views
Human checkable proof of the Four Color Theorem?
Four Color Theorem is equivalent to the statement: "Every cubic planar bridgeless graphs is 3-edge colorable". There is computer assisted proof given by Appel and Haken. Dick Lipton in of his ...
5
votes
1
answer
283
views
Random walk on the hypercube with deleted edges
Let $G$ be the $n$-dimensional boolean hypercube, i.e. the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph $G'$ obtained by deleting a ...
7
votes
1
answer
396
views
Strong tournaments
Let $T$ be a strong tournament, and let $N=v_1v_2 \cdots v_n$ be an enumeration of $V(T)$. Let $C$ be a circuit in $T$. We define $i_N(C)=|\{(v_i,v_j) \in E(C); i>j\}|$. Suppose that $N$ is chosen ...
2
votes
1
answer
150
views
Electrode assignment problem in resistive networks
Main question
In the context of resistor networks, and particularly purely from a graph theory point of view, is there a consistent way of assigning the two electrode nodes in order to compare the ...
5
votes
0
answers
101
views
Dinitz Conjecture extension to rectangles
The Dinitz Conjecture, which was proved later in a more general form by Galvin, stated that given an $n\times n$ array, its elements could be filled exactly like a latin square, where the elements in ...
4
votes
0
answers
277
views
Reference for results about planar graphs
A colleague and I are writing a paper in which we need to make use of some basic facts about planar graphs. I would strongly prefer to simply give references for the results if possible, because the ...
9
votes
0
answers
304
views
Thurston on the Robertson-Seymour theorem
Danny Calegari recounts here that Bill Thurston "gave one talk explaining his idea of a new proof of (some version of) the Robertson-Seymour theorem" at MSRI in 1996-1997. I could not find it in the ...
3
votes
1
answer
195
views
How many graphs of order n, maximum degree k, and maximum diameter d exist?
The total number of simple undirected graphs of order $n$ is
$\sum\limits_{i = 0}^{\frac{n(n-1)}{2}}{\binom{\frac{n(n-1)}{2}}{i}} = 2^{\frac{n(n-1)}{2}}$.
What is the number of simple undirected ...
2
votes
1
answer
172
views
Is this graph problem NP-Hard?
I had asked this question in math.se without any success
Let $A$ be the symmetric $n\times n$ adjacency matrix for a graph where $A_{ij}$ is the positive edge value between node $i$ and $j$ (thus ...
1
vote
1
answer
153
views
Solutions to Diophantine equation for Ramanujan graph construction
I am working with so-called Ramanujan graphs which have the property that a lower bound on their girth can be stated. I am reading about those in paper On the Construction of Turbo Code Interleavers ...
1
vote
0
answers
110
views
Chromatic number of certain graphs with high maximum degree
Let $G$ be the graph of even order $n$ and size $\ge\frac{n^2}{4}$ which is a Cayley graph on a nilpotent group but not complete. Can the chromatic number of this graph be determined in polynomial ...
32
votes
9
answers
5k
views
How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?
Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...
3
votes
1
answer
170
views
Edge coloring graphs is in P?
It is known that there exist polynomial time algorithm to approximate the Lovasz number or the supremum of Shannon capacity of graphs.
By Vizing's theorem, the graph $G$ has only two chromatic ...
5
votes
2
answers
609
views
Computer program for counting graph homomorphisms
I would like to ask is there a computer program for counting graph homomorphisms?
15
votes
7
answers
1k
views
Examples of proofs by making reduction to a finite set [closed]
This is a very abstract question, I hope this is appropriate.
Suppose $T$ is some claim over some infinite set $A$, for example, let $A$ be the set of all loopless planar graphs, and $T$ be the claim "...
2
votes
1
answer
148
views
Define a homomorphism of a set of graphs to its power set
Let $G$ be a simple graph and $S$ be the set of all sub graphs of $G$. Define two operations on $S$ as: $union$ of two graphs $ G_1$ and $G_2$ is,
$G_1\cup G_2$
$=\langle V(G_1)\cup V(G_2), (E(G_1)\...
2
votes
0
answers
510
views
Is there a known proof that $R(5,5)\leq 47$ in Ramsey theory?
As an application to a model describing graphs with partial information, I found what might be an (as yet unverified) proof that $R(5,5)\leq 47$.
According to the Dynamic Survey of Ramsey Numbers at ...
3
votes
1
answer
70
views
Connected hypergraphs
We say that a hypergraph $H=(V,E)$ is connected if the following condition holds:
for all $S\subseteq V$ with $\emptyset\neq S \neq V$ there is $e\in E$ that meets both $S$ and $V\setminus S$, i.e. ...
12
votes
4
answers
578
views
A specific collection of subgraphs in $K_{70, 70}$
Does there exist a collection of subgraphs $\{\Gamma_i\}_{i = 1}^{24}$ of $K_{70, 70}$, that satisfy the following two properties:
1)$\Gamma_i \cong K_{i, i} \forall 1 \leq i \leq 24$;
2)Any edge of $...
6
votes
0
answers
123
views
Squared squares and partitions of $K_{nn}$
This is inspired by a recent question.
Define a square square sum (SSS) of order $n$ to be any partition $$n^2=\sum_1^tc_ii^2 \tag{*}$$ of $n^2$ into square summands. Call it perfect if all $c_i \leq ...
1
vote
0
answers
110
views
Digraphs with same number of semiwalks
This is a follow-up question to Characterisation of walk-equivalent digraphs.
Question: Do there exists two directed graphs $G$ and $H$ consisting of the same number ($n$) of vertices, such that
\...
1
vote
1
answer
135
views
Characterisation of walk-equivalent digraphs
Setting Let $G=(V,E)$ be an undirected graph. A walk $\pi$ in $G$ of length $k$ is a sequence of $k+1$ vertices $v_1,\ldots,v_{k+1}$ such that for each $i\in[1,k]$,
$\{v_i,v_{i+1}\}\in E$. Let $H=(W,F)...
1
vote
0
answers
265
views
Definition of k-partite hypergraph
I would like to know the standard definition of k-partite hypergraph.
There are two natural generalizations of k-partite graph to k-partite hypergraph:
1. For all edges e, any two vertices in e are ...
1
vote
1
answer
259
views
History of the Vertex Disjoint Cycle Cover with Minimal Edgeweight Sum
Questions:
who first posed the problem of determining a collection of (directed) cycles, whose edgeweight sum is minimal and, for which each vertex belongs to exactly one of the cycles?
who came up ...
-6
votes
2
answers
543
views
Do degrees determine the chromatic number?
Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex sets $\varphi:V(G) \to V(H)$ such that for all $v\in V$ we have $$\text{deg}_G(v) = \deg_H(\varphi(v)).$...