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.

-3
votes
1answer
71 views

Maximum chromatic number of a $k$-regular graph

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
41 views

Regular graph such that $2$ distinct vertices have same neighborhood set

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 ...
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 ...
6
votes
0answers
111 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 ...
-1
votes
1answer
63 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{ ...
-1
votes
1answer
104 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\...
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
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
15 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 ...
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 ...
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 ...
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 ...
4
votes
1answer
95 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 ...
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) \...
11
votes
1answer
276 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: ...
3
votes
1answer
129 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 ${\...
1
vote
1answer
59 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 ...
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 ...
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 ...
5
votes
2answers
283 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
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 ...
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 ...
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 ...
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 ...
1
vote
0answers
29 views

Is there an algorithm for this constrained Hypergraph optimization problem?

I'm currently developing an algorithm for computing knot coloring invariants and got to the following question: Given a set $S$ and a certain hyper-graph $H \subseteq S^3 $, find a decomposition $S = ...
0
votes
1answer
51 views

Estimating Maximal-Clique of Metric Graphs via the Rank of their Adjacency Matrix

Let $\mathrm{M}\in\lbrace0,1\rbrace^n$ be the adjacency matrix of a graph $\mathrm{G}\left(V,E\subseteq\lbrace\lbrace u,v\rbrace| u,v\in V\rbrace\right)$ of order $n$. Let $\mathrm{G}$ ...
0
votes
1answer
84 views

Chromatic Polynomials of Circulant Graph With Two Parameters

I have been working with the chromatic polynomials of circulant graphs of prime order $p$ with two distinct parameters, i.e. $P_{p,i,j}(x):= P(C_{p}(i,j),x)$ with $1 \leq i \neq j \leq \ n/2.$ In ...
7
votes
1answer
146 views

Terminology for expressing a graph as a sum of cliques (mod 2)

I am interested in the problem of expressing the edges of a given (undirected, simple) graph as the sum of edge sets of cliques modulo $2$. To be more concrete, given a graph $G=(V,E)$, I am seeking ...
1
vote
1answer
71 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 ...
0
votes
3answers
97 views

Clustering on tree

I am looking for a method that would identify clusters in a tree-like structure. In the figure below you can see a very simple example where one can visually identify distinct branches with a lot of ...
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 ...
1
vote
1answer
95 views

Is every finite graph isomorphic to the proximity graph of some $S\subseteq \mathbb{R}^n$?

This is the question that I should have asked before asking this older question. If $(X,d)$ is a metric space, we associate with it a simple, undirected graph, called its proximity graph $G(X,d)$ ...
11
votes
1answer
154 views

Connected incomparability graph

Let $X$ be a finite set equipped with a partial order. (Not a preorder: $a < b$ implies $b \not< a$.) The corresponding incomparability graph has vertex set $X$ with an edge between two points ...
2
votes
1answer
69 views

Spatial dimension of a finite graph

If $(X,d)$ is a metric space, we associate with it a simple, undirected graph, called its proximity graph $G(X,d)$ given by $V(G(X,d)) = X$ and $$E(G(X,d)) = \big\{\{x,y\}:x\neq y\in X \text{ and } d(...
3
votes
0answers
56 views

Name of a binary matroid coming from the cycle space of a graph

In some of my recent work, I have 'discovered' a binary matroid which I will describe below. Given a graph $G$, let $H_1(G, \mathbb{Z}/2\mathbb{Z})$ denote the cycle space. This is a vector space ...
2
votes
1answer
108 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 ...
1
vote
1answer
36 views

Does $G$ with $\delta(G)\geq \aleph_0$ contain $k$-regular sub-edge-sets?

Let $G=(V,E)$ be an infinite, simple, undirected graph, such that for all $v\in V$ we have $\text{deg}(v) \geq \aleph_0$. Given an integer $k\geq 1$, is there always $E^{(k)}\subseteq E$ such that $(V,...
1
vote
1answer
51 views

Some questions about a family of regular undirected graphs

Let $S$ be the regular n-dimensional simplex. We create a graph of where the vertices are m-faces and two vertices are connected if there exist a common (m-1)-face which they share. Then the number of ...
1
vote
0answers
84 views

Find a graph when given length-k paths?

I have an undirected connected graph $G$ and I have a matrix $S^{(k)}$ were $S^{(k)}_{i,j}=1$ if there is a length-$k$ path between $i$ and $j$ and 0 otherwise. Now, $S^{(1)}$ is then simply the ...
0
votes
1answer
48 views

On the formal definition of mesh or region for a planar graph

A graphical representation of a planar graph divides the plane into regions or meshes (as they are called in certain applications, e.g. in circuit theory). Yes, the above fact is intuitive, but what ...
3
votes
0answers
36 views

Reference on generalization of plane graph duality between bonds and simple cycles

Let $G$ be a plane graph, and $G^*$ its dual. Among the $k$ partitions of the nodes of $G$, I'll call the connected k-partitions those such that each block of nodes of the partition induces a ...
0
votes
2answers
112 views

Vertex Connectivity of the Hypercube [closed]

I am revising my lecture notes about connectivity, but I am stuck regarding proof of $κ(Q_d) = d$ Then I took a look of the proof by induction in D. West's book. For $d\leq1$, $Q_d$ is a clique with $...
7
votes
1answer
129 views

Going up of an amalgamated decomposition of a subgroup of finite index

Let $G$ be a finitely presented group and H a subgroup of index $n$ in $G$. Suppose that H has a non-trivial decomposition as amalgamated product, say $H = A \ast_U B$. I am wondering about the ...
4
votes
1answer
143 views

existence of a certain subset of vertices in a graph

Take an undirected graph $G=(V,E)$. For any subset $M\subseteq V$, we define ${\rm deg}_M(v)=|\{k\in M:(v,k)\in E\}|$, namely, the number of neighbors of $v$ in $M$. Is it true that, there exists a ...
0
votes
2answers
85 views

Does Max Flow produce uniform results? [closed]

I am interested in using Max Flow algorithm. I want to simulate transfer of quantity. Anyway, I am unsure of some thing. Does Max Flow algorithm produce uniformly distributed max flow? I have ...
0
votes
1answer
70 views

Minimizing the set of “wrong” edges in $K_\omega$ with $\{0,1\}$-weights

For any set $X$, let $[X]^2 = \big\{\{x,y\}:x\neq y\in X\big\}$. Let $f:[\omega]^2\to\{0,1\}$ be a function. The principal goal is to find a partition of $\omega$ such that if $m\neq n\in \omega$ ...