Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
3answers
90 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 ...
6
votes
1answer
104 views

Strongly rigid regular graphs

A simple, undirected graph $G = (V,E)$ is said to be strongly rigid if the identity is the only graph endomorphism. For which positive integers $k>2$ is there a strongly rigid $k$-regular graph?
-3
votes
1answer
78 views

Maximum chromatic number of a $k$-regular graph [on hold]

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
1answer
56 views

Regular graph such that $2$ distinct vertices have same neighborhood set [on hold]

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
1answer
413 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 ...
1
vote
1answer
72 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 ...
6
votes
0answers
148 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 ...
0
votes
0answers
74 views

How to prove the exact top degree of the polynomial coming from each Feynman diagram?

Let $W=x_0+x_1+x_2+\lambda_0 \ln(x_0)+\lambda_1\ln(x_1)+\lambda_2\ln(x_2)+(\frac{x_0x_1x_2}{q})^{\frac{1}{3}}$, where $\lambda_i=\xi^i\cdot\lambda$, $\xi$ is the 3-th root of unit. For each Feynman ...
11
votes
1answer
281 views

To find a longer path with fixed endvertices in a graph satisfies the following property

Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where $$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$ I found that if the path $P$ satisfies: ...
6
votes
0answers
112 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
0answers
28 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 ...
-1
votes
1answer
64 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
1answer
113 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
votes
1answer
107 views

Version of Hall's marriage theorem in arbitrary finite graphs [closed]

Let $G=(V,E)$ be a finite, simple, undirected graph such that $\bigcup E = V$ (that is, every vertex belongs to at least one edge). For $v\in V$ we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and for $S\...
15
votes
1answer
277 views

Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...
11
votes
4answers
930 views

Is there a Cayley graph of a non-abelian finite group that is not isomorphic to any Cayley graph of any abelian group?

It's the first question I post here :) I'm sorry if the question is too specific or if it's somehow repeating others. In other words, my question is the following. Consider a Cayley graph $\Gamma$ of ...
1
vote
0answers
32 views

Hypergraph partitioning and bipartite graph partitioning

Are hypergraph partitioning, and bipartite graph partitioning related, or equivalent, given that hypergraphs can be represented as bipartite graphs? In the first case, we want to partition the set of ...
0
votes
0answers
16 views

Hypergraph mapping's projection

I have been struggling quite a while with a question, which I suspect might have a simple answer to: I have a Graph G = (X,E,Ψ) with E (hyperedge) being a family of subsets of X and Ψ being a mapping ...
2
votes
0answers
51 views

Total Coloring Conjecture for Cayley Graphs

The total Coloring Conjecture(TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...
0
votes
1answer
201 views

How to find a random cycle in a large graph?

Suppose we have a large directed graph $G$ with no self-cycle and no more than one edge between two nodes, for example, containing about 2000 nodes and about 10 edges per node. Now we need to achieve ...
5
votes
1answer
233 views

Finding a semi-sparse vertex in a grid

Let $H$ be a $r \times r$ grid. Suppose that at most $r/10^5$ vertices of this grid are colored red. For every vertex $v \in V(H)$, let $B_i(v)$ be the ball of radius $i$ centered at $v$. (Or for ...
2
votes
0answers
45 views

Obtaining the reduced incidence algebra in QPA

Given a finite poset $P$ (we can assume it is connected), the reduced incidence algebra of $P$ is the subalgebra of the incidence algebra of $P$ consisting of functions constant on isomorphic ...
0
votes
1answer
78 views

Average Edge-cost Optimality of MSTs

Are there counter examples to the conjecture, that in a complete, finite and symmetric weighted graph $G\left(V,E,\omega\right),\ E=\lbrace \lbrace i,j\rbrace\subset V\times V\rbrace,\ \omega:E\ni e\...
1
vote
0answers
61 views

Are there half-transitive convex polytopes?

I only consider convex polytopes, i.e. convex hulls of finitely many points. The (edge-)graph of a polytope $P\subseteq\Bbb R^d$ is the graph consisting of the polytope's vertices, two are adjacent if ...
9
votes
1answer
1k views

Origin of the banana graph

The graph with two vertices and $n > 1$ edges connecting them has been called the "banana graph" in a number of papers. For one example, see "Feynman Motives of Banana Graphs" by Aluffi and Marcoli,...
0
votes
0answers
59 views

Lower bound on the nonzero Laplacian eigenvalue with the smallest real part

Consider a directed graph with $n$ vertices. The graph is not assumed to be connected, and therefore the multiplicity of the eigenvalue 0 may be greater than 1. I am looking for a nonzero lower bound ...
6
votes
2answers
745 views

Do you know a faster algorithm to color planar graphs?

while studying the four color theorem, I implemented an algorithm (in Python and Sage) that can color planar graphs much faster than the implementations I found around on internet. The program can be ...
4
votes
1answer
96 views

Hamming representability of finite graphs

This is a follow up on an older question. We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of ...
1
vote
1answer
97 views

On a theorem of Chetwynd and Hilton in Graphs

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
0
votes
1answer
102 views

Conjecture on representing graphs within $\{0,1\}^n$

We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of the set $\{ i \in \{0, ..., n-1\} : x(i) \...
3
votes
1answer
130 views

Induced minors of $\{0,1\}^\omega$

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 ${\...
2
votes
1answer
236 views

H-generalized join graph

The $A$-join of a set of graphs $\{ G_a \}_{a \in A}$ as‎ ‎the graph $H$ with vertex and edge sets‎ ‎\begin{eqnarray*}‎ ‎V(H) &=& \{(x,y) \ | \ x \in V(A) \ \& \ y \in V(G_x) \},\\‎ ‎...
0
votes
1answer
79 views

Is there any solution that currently exists for the graph automorphism problem in the general case?

I was reading the Wikipedia pages on the graph automorphism, but I could not find any solution to the problem (Not even a brute force one). So, is it indeed true that no solutions exist for the ...
1
vote
1answer
60 views

Enumerating isomorphic subgraphs

For digraphs $G$ and $H$ if we can partition $V(G)$ into a family $\{Q_t\}_{t\in V(H)}$ indexed by $V(H)$ such that $E(G)=\bigcup_{(u,v)\in E(H)}Q_u\times Q_v$, then is every subgraph of $G$ ...
3
votes
1answer
67 views

Generalized digraph homomorphisms and graph cores

Given any digraphs $G$ and $H$ we say a surjection $f:V(G)\to V(H)$ reduces $G$ to $H$ if and only if it satisfies $(u,v)\in E(G)\iff (f(u),f(v))\in E(H)$. Where if there exists at least one ...
5
votes
2answers
284 views

The number of Dyck paths of length $2n$ and height exactly $k$

In A080936 gives the number of Dyck paths of length $2n$ and height exactly $k$ and has a little more information on the generating functions. For all $n\geq 1$ and $\frac{(n+1)}{2}\leq k\leq n$ we ...
1
vote
1answer
179 views

Bounds on degrees of minors obtained by edge contractions of regular graphs

Given a connected $d$-regular graph $G=(V,E)$, generate a sequence of minors by performing only edge contractions and loop deletions (as, e.g., in Karger's algorithm) until the graph collapses to a ...
8
votes
5answers
11k views

How to find central vertex in a graph?

I am learning graph theory and some concept that I cannot figure it out. A vertex is central in $G$ if its greatest distance from any other vertex is as small as possible. Is there any algorithm to ...
2
votes
1answer
42 views

Is it true that centrality measures in SNA are indicative for most important vertices only?

I read about the limitations of centrality measures on Wikipedia. It says that centrality measures are good only for identifying top most important nodes in a social network. Their relative values can ...
0
votes
1answer
71 views

Finding a good transversal basis

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...
4
votes
1answer
147 views

The existence of a specific kind of independent set in a connected graph satisfying the following property

Suppose $G$ is a connected finite graph satisfying that every edge $uv$ of $G$ belongs to a "triangle" $uvw$ such that $uv,uw\in E(G),\ vw\notin E(G)$ or $uv,vw\in E(G),\ uw\notin E(G)$(in other words,...
0
votes
3answers
189 views

Is every graph an incomparability graph?

Let $G=(V,E)$ be a simple, undirected graph. Is there a partial ordering $\leq\subseteq (V\times V)$ with the following property? $$\{v,w\} \in E \text{ if and only if } v||y$$ (We write $v||w$ in ...
5
votes
1answer
73 views

Cut sets in 2-connected 3-regular graphs?

I believe that I have a result that is well known by someone here. If you know where I can find a proof, then I would appreciate it. It seems like elementary graph theory, but I have not been able ...
3
votes
1answer
100 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 $\...
0
votes
1answer
96 views

Description of Linear Time Algorithm for TSP in Halin Graphs

I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in "G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...
8
votes
0answers
349 views

Colored weighted Graphs with only monochromatic perfect matchings

The following purely graph-theoretic question is motivated by quantum mechanics. Definitions: A bi-colored weighted graph $G(V,E)$ is an undirected graph where every edge is colored, and has a ...
0
votes
0answers
40 views

Examples of Binary Functions that Yield Regular Graphs with Invertible Adjacency Matrix

Question: What are, provided their existence, examples of functions $f$ with the following properties: \begin{align}f:& \ \mathbb{N}\times\mathbb{N}\ni(i,j)&\mapsto\ \quad\quad\...
4
votes
1answer
211 views

Applications of De-Bruijn Sequences in “Pure Mathematics”

I know of a few applications of De-Bruijn Sequences and De Bruijn Graphs in combinatorics, applied mathematics, Engineering and computer science. But I have only found one application of De Bruijn ...
4
votes
1answer
756 views

New edge coloring problem in graph theory

Let $G$ be a simple graph. Consider the following edge coloring: We are allowed to use repetitive colors on some edges incident to a vertex such that the result does not contain a sequence of length $...
2
votes
1answer
61 views

Genus for specific family of graphs

We are looking for graphs with certain properties that have a specific genus. We constructed a simple family, but now realised that we actually only have an upper bound for the genus. Is there an easy ...