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.

Filter by
Sorted by
Tagged with
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)).$...

1
35 36
37
38 39
103