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
3
votes
0
answers
1k
views
Matrix Operations Preserving Hurwitz Stability
I begin with terminology I use in the question. A real square matrix $A$ is
negative-stable if for every eigenvalue $\lambda$ of $A$, ${\mathrm{Re}}(\lambda) < 0$;
$\ast$-negative-stable if for ...
2
votes
0
answers
150
views
Graph pattern matching
Given a weighted, oriented, connected graph with $10^7$ vertices and $10^{10}$ edges I need to implement the algorithm for searching various patterns on this graph for less than polynomial time.
...
0
votes
1
answer
43
views
Connected subgraph of infinite graph with surjective homormophism, but no graph isomorphism
For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$.
What is an example of a connected graph $G=(V,E)$ and a subset $S\subseteq V$ such that the subgraph $$G[S]:=(S, E\cap [S]^2)$$ is ...
1
vote
1
answer
75
views
The complexity on calculation of the Graev metric on the free Boolean group of a metric space
For a set $X$ by $B(X)$ we denote the family of all finite subsets of $X$ endowed with the operation $\oplus$ of symmetric difference. This operation turns $B(X)$ into a Boolean group, which can be ...
5
votes
1
answer
1k
views
Intuition on Kronecker Product of a Transition Matrix
Let $T$ be a $N\times N$ transition matrix for a markov chain with $N$ states. Thus $T_{ij}$ is the probability of transition from state $i$ to state $j$ (and thus rows summing to one). Now consider ...
1
vote
1
answer
346
views
When is MAXCUT "easy"?
MAXCUT is NPC but is known to be polynomial for, say, planar graphs.
Are there any other graph families where it is known MAXCUT is polynomial?
(Please don't say "bipartite graphs" :) )
0
votes
1
answer
85
views
Linear intersection number and chromatic number for infinite graphs
Given a hypergraph $H=(V,E)$ we let its intersection graph $I(H)$ be defined by $V(I(H)) = E$ and $E(I(H)) = \{\{e,e'\}: (e\neq e'\in E) \land (e\cap e'\neq \emptyset)\}$.
A linear hypergraph is a ...
0
votes
0
answers
56
views
Are total graph of power of cycles homeomorphic to powers of cycles?
Is the total graph associated to powers of cycles homeomorphic to powers of cycles themselves?
I think yes, because the total graph associated to cycles is homeomorphic to cycles(i think?)So, does ...
0
votes
1
answer
51
views
Minimizing the set of "faulty" edges in a map between the vertex sets of $2$ graphs
The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$.
...
3
votes
2
answers
516
views
Packing vertices on a hypercube graph?
Imagine a graph where the vertices and edges model an n dimensional hypercube (a line, a square, a cube and so on). A red vertex must have a minimum distance of 3 from every other red vertex. The ...
3
votes
0
answers
114
views
Reference Request: simple graph vertex labelings with balanced induced edge weights
Say that the edge weight induced by a vertex labeling is the sum of the weights of the two vertices comprising it. Here is the problem of interest: given a simple $d$-regular graph $G = (V,E)$, find a ...
1
vote
1
answer
48
views
Tightly knit graphs on $\omega$
We say that a simple, undirected graph $G = (\omega, E)$ on the vertex set $\omega$ is tightly knit if there is a positive integer $n>2$ such that for all $v,w\in \omega$ there is a cycle $C$ of ...
7
votes
5
answers
2k
views
On the spectrum of random regular graph
For a random $d$-regular graph, where $d$ can be fixed or can grow slowly with the size of the graph $n$, what can we say about its spectrum - Do you believe it has simple spectrum?
Thank you,
4
votes
1
answer
173
views
Graphs that are not $\mathbb{R}^2$-realizable
We say that a finite, simple, undirected graph $G=(V,E)$ is $\mathbb{R}^2$-realizable if there is an injective map $\varphi:V\to \mathbb{R}^2$ such that for $v\neq w \in V$ we have $\{v,w\} \in E$ if ...
3
votes
1
answer
267
views
Does every directed graph have a directed coloring with $4$ colors?
Every finite directed graph has a majority coloring with $4$ colors. (The notion of majority coloring is defined below.)
Question. Can every infinite directed graph be majority-colored with $4$ ...
6
votes
1
answer
270
views
Does every bijective graph endomorphism restrict to a full-cardinality isomorphism?
Given a graph $G$, and a bijective endomorphism $f$ (that is, a graph homeomorphism $f : G \to G$ that establishes a bijection on the vertices), it is true that $f$ is an automorphism whenever $|G|$ ...
1
vote
0
answers
33
views
Name for a Lower Bound on the Length of General TSPs and ATSPs
Let $G\left(\ V,\ E=V\times V\setminus\lbrace(v_i,v_i)\rbrace,\ \Omega: E\ni e_{ij}\mapsto\omega_{ij}\in\mathbb{R}\right)$ be a(n) (A)TSP instance.
Then
$$2*\ell(T_{\mathrm{opt}})\quad\ge\quad\sum_{v\...
1
vote
0
answers
81
views
Treewidth problem equivalence
Say we are solving a tree decomposition problem, e.g.
given a graph $G = (V, E)$ we try to find a chordal graph $H$ such that $V(H) = V(G)$, $E(G) \in E(H)$ and the maximal clique in $H$ is minimal ...
1
vote
0
answers
37
views
What is the Advantage of 1-trees over Vertex Splitting?
It is a wellknown fact that the problem of finding an optimal Hamilton tour is equivalent to finding an optimal Hamilton path after a small modification of the problem instance, namely splitting one ...
3
votes
1
answer
120
views
The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles
Let $c(n,k)$ be the least integer such that if $G$ is a simple graph on $n$ vertices with $n + c(n,k) - 1$ edges then $G$ has $k$ edge-disjoint cycles.
Clearly, $c(n, 1) = 1$ and it not very hard to ...
14
votes
1
answer
982
views
Are all cubic graphs almost Hamiltonian?
Call a graph $G$ $n$-almost-Hamiltonian if there is a closed walk in $G$ that visits every vertex of $G$ exactly $n$-times. So a Hamiltonian graph is $n$-almost-Hamiltonian for all $n$. Are all ...
3
votes
1
answer
394
views
Projective graphs
Let the category $\mathbf{Gr}$ consist of simple, undirected graphs, together with graph homomorphisms. We say that a graph $P$ is projective if for all graphs $A, B$ with a surjective graph ...
0
votes
1
answer
103
views
Increasing Hadwiger number by collapsing vertices of distance $2$
If $G=(V,E)$ is a finite, simple, undirected graph, the Hadwiger number $\eta(G)$ is defined to be the size of the largest complete minor of $G$.
Is there a finite graph $G=(V,E)$ with the following ...
2
votes
1
answer
527
views
Component size distribution in small Erdos-Renyi networks
I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10.
I would like to know the probability a random node is in a component of size $m$.
It's ...
5
votes
2
answers
530
views
"Locally Nonplanar" graph
A 2-connected $3$-connected graph $G$ is "Almost Planar" Locally Nonplanar if it has a a $2$-connected spanning subgraph $H$ and an embedding in the plane such that $H$ is planar in this embedding and ...
1
vote
1
answer
152
views
Extension of chromatic polynomial to multi graphs
Let $G$ be a multigraph, i.e, there can be more than one edge between a pair of vertices. It is clear that the chromatic polynomial cannot capture these multi-edges. Because chromatic polynomial just ...
7
votes
2
answers
404
views
Graph which do not satisfy a pseudo-Poincaré inequality
Say that an infinite (connected) graph (with vertices of bounded degree) satisfies a $\ell_1$-pseudo-Poincaré inequality if there is a constant $C>0$ so that for any $n \in \mathbb{N}$ for any ...
1
vote
1
answer
112
views
Graphs formed of vertices of distance $2$
Let $G=(V,E)$ be a finite, simple, undirected graph. Let $D_2(G)$ be the graph with vertex set $V$, and two vertices form an edge if and only if they have distance $2$ in the original graph $G$.
...
6
votes
1
answer
303
views
Operad structure on Kontsevich's admissible graphs
In his celebrated 97' preprint q-alg/9709040, M. Kontsevich constructs a $L_\infty$-quasi-isomorphism $\mathcal U:\mathcal D_{\rm poly}\to\mathcal T_{\rm poly}$ between the differential graded algebra ...
2
votes
0
answers
30
views
Graph vertex label dynamics, statistical model reference request
I am modeling some type of social interaction, and came up with the following natural question.
Let $K_n$ be the complete graph on $n$ vertices, with some initial edge labeling in some alphabet $A$.
...
0
votes
1
answer
102
views
Name for Directed Edges in Digraphs
Graph theory originated in German speaking countries and there directed edges are called "Pfeil" which translates to "arrow", which makes sense, because arrows have distinguishable ...
1
vote
1
answer
89
views
Total Chromatic Number of Regular Bipartite Graphs [closed]
What can we say about the total chromatic number of regular bipartite graphs that are not complete? Can we say they are of type 1[Total Colorable(no adjacent/incident elements have same color) by $\...
0
votes
0
answers
87
views
nauty/traces orbit sizes for colored graph?
I'm given a graph $G$ (<1000 vertices, large automorphism group), and a large number (~10^6-10^10) of different colorings of said graph. I have two tasks.
Calculate the canonical coloring. I can ...
4
votes
1
answer
709
views
Graph isomorphism by invariants
Graph isomorphism is known to be a difficult computational problem. The problem get even worst if we want to find non-isomorphic graphs in a large family of graphs.
Let us call a (numerical) ...
4
votes
1
answer
138
views
Asymptotic colouring of edges and vertices, and untwisting cocycles
This question regards colourings on edges and vertices on countable directed multigraphs.
We start with an example. Let $G=\mathbb Z^2$. We define two functions $a_h$ and $a_v$ from $\mathbb Z^2$ to $\...
1
vote
2
answers
279
views
Total Coloring of even regular bipartite graphs
Consider an even order, balanced(both partitions have same vertices) bipartite regular graph of order greater than or equal to $12$ and degree atleast six and divisible by $6$. Then is the graph of ...
8
votes
1
answer
214
views
What is known about graphs that permit only one colouring?
Some graphs ($K_n$ or $K_n$ minus any one edge, for instance) only permit one minimal colouring up to different labels of the colours. Is there anything known about these kind of graphs? I can think ...
0
votes
1
answer
171
views
Is every finite graph an induced minor of $\omega^2$?
Let $G=(V,E)$ be a simple, undirected graph. Suppose that ${\cal S}$ is a collection of non-empty, connected, and pairwise disjoint subsets of $V$. Let $G({\cal S})$ be the graph with vertex set ${\...
3
votes
1
answer
729
views
Open Problems in Random Graphs [closed]
I am a PhD student in mathematics. I'm interested in probabilistic methods in combinatorics and especially random graphs. I am looking for an open problem in this area for my PhD proposal. I know that ...
4
votes
4
answers
265
views
Bijective operations on finite simple graphs
Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An ...
7
votes
1
answer
139
views
equidistributed parameters on graphs
Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I wonder whether there are any 'interesting' combinatorial parameters $a,b: \mathcal G_n\to \mathbb ...
-3
votes
1
answer
966
views
Maximum chromatic number of a $k$-regular graph [closed]
Let $c_k$ be the maximum chromatic number that a $k$-regular graph can have. What is $\lim\sup_{k\to\infty}\frac{c_k}{k}$?
-4
votes
1
answer
100
views
Regular graph such that $2$ distinct vertices have same neighborhood set [closed]
If $G=(V,E)$ is a simple, undirected graph and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$.
Is there an integer $k>1$ and a connected $k$-regular graph $G=(V,E)$ such that there are $v\neq ...
0
votes
1
answer
627
views
Literature about most basic existence proofs in graph theory [closed]
I'm writing a MIZAR article about foundations in graph theory e.g. constructing a supergraph from a given graph by adding a vertex to it. The main theorem of the article will be that any graph ...
2
votes
1
answer
86
views
Literature on the controllability of networks under attack
I would like to request your advice on a problem arising from my research in the life sciences. Consider a modular, sparse weighted network which is partially controllable in the sense that some ...
9
votes
0
answers
258
views
How sensitive are Neural Networks to weight change?
Let's consider the space of feedforward neural networks with a given structure: $L$ layers, $m$ neurones per layer, ReLu activation, input dimension $d$, output dimension $k$.
Which means I'm ...
8
votes
0
answers
432
views
Is there a version of Weyl's law for graph Laplacians?
Is there a version of Weyl's law or a local Weyl's law for eigenvectors of the graph Laplacian?
For some context, a colleague in statistics has encountered eigenvectors of the Laplacian for certain ...
2
votes
0
answers
54
views
Flat or linkless embeddings of graph with fixed projection
The problem of finding whether a given planar diagram of a graph, with over- and under-crossings, is a linkless embedding or not has unknown complexity (Kawarabayashi et al., 2010). My first question ...
0
votes
1
answer
91
views
$2n$-regular graphs with maximal chromatic number
Let $n\geq 1$ be an integer. Suppose $m\geq 2n+1$ is an integer. We construct the graph $\mathbb{Z}_m = (\mathbb{Z}/m\mathbb{Z}, E_m)$ where $$E_m=\big\{\{x,y\}:x, y \in \mathbb{Z}/m\mathbb{Z} \text{ ...
2
votes
1
answer
243
views
Minimum dominating sets in tournaments
It is known that in any tournament with $n$ vertices, there is a dominating set of size no more than $\lceil \log_2 n\rceil$. (See Fact 2.5 here.)
What about when the tournament is chosen ...