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
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 ...

1
41 42
43
44 45
103