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
1
vote
1answer
90 views

Existence of connected component with large boundary?

Question 1. Let $\Gamma=(V,E)$ be a connected graph with $n$ vertices, all of degree $d\geq 4$. Assume every vertex has $d$ distinct neighbors. (We can think of $d$ as being much smaller than $n$, ...
3
votes
1answer
45 views

For which sets of $(n, m, k)$ does there exist an edge-labelling (using $k$ labels) on $K_n$, such that every single-labelled subgraph is $K_m$?

Or, equivalently - for what sets of $(n, m, k)$ is it possible, for a group* of $n$ people, to arrange $k$ days of "meetings", such that every day the group is split into subgroups of $m$ people, and ...
9
votes
0answers
150 views

Direct combinatorial link between Sperner's and Tucker's Lemma?

Sperner’s Lemma is often called the "combinatorial analog" of Brouwer’s Fixed Point Theorem, and similarly Tucker’s Lemma is often called the combinatorial analog of Borsuk–Ulam’s Theorem. Even ...
0
votes
0answers
27 views

Complexity of edge coloring of class 1 graphs

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it ...
2
votes
0answers
33 views

Path-covering for vertex-transitive graphs

I have the following dummy problem: Claim - There exists $N$ such that for $n > N$, if $G_n$ be a connected directed vertex-transitive graph with $n$ vertices, then there exists a set $S$ of paths ...
1
vote
0answers
34 views

Counting number of special subset of vertices in a tree

As defined in this article, an ordered pair $ (X,Y) $ of disjoint subsets of the vertices of a graph $ G $ with $ \vert X \vert = \vert Y \vert =2 $, is called an odd pair if the number of edges with ...
1
vote
0answers
51 views

Graphs with vanishing homology and behaviour of the suspension of that graphs

Let $G$ be a simple graph. The clique complex, $\Delta(G)$ of the graph $G$ is the simplicial complex given by the collection of all complete subgraph of $G.$ Now we define the graph homology $H^{Gr}_\...
4
votes
0answers
41 views

Bandwidth of two-dimensional grid graphs

Suppose that $G$ is a subgraph of the two-dimensional grid and there are $n$ vertices in $G$. What is the maximum possible graph bandwidth of $G$ as a function of $n$? If $G$ is a square grid graph ...
-4
votes
0answers
30 views

how to find out a node that is not reachable from other nodes in a list and then add an edge b/w that node and a random node in python [closed]

I have an adjacency matrix of graph G=(V,E) and a list of nodes 'v' subset of V. Now I want to find out node/nodes of 'v' that is/are not reachable from other nodes of 'v' and then adding an edge ...
-1
votes
1answer
63 views

Effect of collapsing two vertices of distance $2$

Motivating example. Consider the graph $G=(V,E)$ with $V = \{0,1,2,3\}$ and $E = \big\{\{i,i+1\}: i\in \{0,1,2\}\big\}$. We have $\chi(G) = 2$, but if we collapse $0$ and $3$, we get the complete ...
0
votes
0answers
24 views

Clustering coefficient in a directed graph

I am wondering what the meaning of the clustering coefficient in a directed graph. I know how to calculate it: local clustering coefficient formula, retrieved from [Wikipedia]1 and I know how to ...
0
votes
1answer
31 views

Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques

Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
1
vote
0answers
26 views

Finding minimum weight perfect matchings in sparse bipartite graphs

Question: What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values? I am looking for ...
7
votes
1answer
409 views

Boundedness of total current in electrical network

Consider the following symmetric matrix (adjacency matrix): $$A=(a_{ij})_{1\leq i,j\leq n}$$ such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{...
1
vote
0answers
44 views

What is known about this generalization of planar dual?

So it is well known that given a planar graph, $G$, embedded in the plane (without edge crossing, so a planar embedding). One can construct the planar dual, $G^*$. What is perhaps slightly less well-...
1
vote
1answer
131 views

Cayley graphs do not have isolated maximal cliques

Let a Cayley graph $G$ of a group $H$ with respect to the generating set $\{s_i\}$ have a clique of order $> 2$. In addition assume the graph $G$ is non-complete. If the clique size is less than ...
11
votes
2answers
290 views

Exponential decay of voltage potential difference

Consider the following adjacency matrix of a complete graph: $$A=(e^{-|i-j|})_{1\leq i\neq j\leq n}$$ with 0 on the diagonal. Let $D=diag\{d_1,...,d_n\}$ be the degree matrix where $d_i=\sum_{j\neq i}...
1
vote
0answers
54 views

What is the standard definition of dual of disconnected planar graph when underlying graph derives 'product structure' over connected graphs?

Dual graph of a plane graph has a standard definition https://en.wikipedia.org/wiki/Dual_graph and an edgeless graph on $n$ vertices is planar. What is the standard dual graph of such a graph? Update ...
61
votes
28answers
5k views

Proofs where higher dimension or cardinality actually enabled much simpler proof?

I am very interested in proofs that become shorter and simpler by going to higher dimension in $\mathbb R^n$, or higher cardinality. By "higher" I mean that the proof is using higher dimension or ...
0
votes
0answers
34 views

Average number of edges of an induced graph by using the edge-based node selection technique on a graph with arbitrary degree distribution

Let $G(U,V,E)$ be a simple, undirected, bipartite graph and $U=\{u_1,u_2,{\cdots},u_n\}$ and $V=\{ v_{1},v_{2},\cdots,v_{n}\}$. Let $d_k^l$ be the number of vertex with degree $k$ in $l$, where $l \in ...
2
votes
1answer
61 views

Critical probability for Erdos-Renyi digraphs to be strongly connected

Given $p \in [0,1]$, an Erdos-Renyi graph ${ER}(n,p)$ on $n$ vertices is constructed by defining, for each unordered couple of distinct vertices ${i,j}$ an edge between $i$ and $j$ with probability $p$...
1
vote
0answers
10 views

maximal k-partite subgraph in a complete multipartite graph

What is the maximum number of edges a $k$-partite subgraph of a complete $s$-partite graph can have? Bests, Josefran
1
vote
1answer
151 views

Do there exist graphs whose adjacency matrix is positive semi-definite? [closed]

If so, could you provide examples and specify the conditions under which this occurs? Thank you in advance
3
votes
0answers
162 views

Probability that a random multigraph is simple

Question. Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...
1
vote
1answer
92 views

Explanation of a proof of an embedding lemma of Bollobas and Thomason

I do not understand the proof of Bollobas and Thomason of an embedding lemma. There is a lot of notation to present first, then the statement of the lemma, then the precise question about the proof. ...
7
votes
0answers
252 views

Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?

Is the following lemma a well known result in graph theory? I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
2
votes
0answers
23 views

Automated rewriting of string diagrams in symmetric monoidal categories

Many algebraic structures, such as Frobenius algebras, or quasi-triangular Hopf algebras, can be formulated in an arbitrary symmetric monoidal category. They are given by a collection of morphisms, ...
2
votes
0answers
33 views

eigenvectors of a graph Laplacian VS Fourier basis

Could you please illustrate the following statement: the eigenvectors of a graph Laplacian behave similarly to a Fourier basis, motivating the development of graph-based Fourier analysis theory.
1
vote
1answer
72 views
+100

Max weighted matching where edge weight depends on the matching

Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...
3
votes
1answer
65 views

The effects of collapsing vs joining non-adjacent vertices on the chromatic number

For any set $X$, let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$. Is there a finite, simple, undirected, connected graph $G=(V,E)$ with the following properties? There is $\{v, w\}\in [V]^2\...
0
votes
0answers
10 views

Finding weight minimal swap-free directed vertex covers

Suppose a complete directed graph is given with $n$ vertices and $n(n-1)$ weighted arcs $a_{ij}$ and we have $\omega(a_{ij}\ne\omega{a_{ji})$ for at least one pair of antiparallel arcs and the ...
2
votes
0answers
115 views

Graphs which are built from complete graphs : Reference request

Let $V$ be a set of $n$ vertices. Fix $3 \le k \le n$. Let $\binom V k$ be the set of all $k$ element subsets of $V$. We add the edges in $V$ as follows: Let $\mathcal S \subseteq \binom V k$ be ...
2
votes
0answers
44 views

The expected size of a subtree of any labelled rooted tree

Consider the set of labelled rooted trees of size $n$, $\mathcal{T}_n$. Let $r$ be the root of each tree $T=(V,E)\in\mathcal{T}$, $r\in V(T)$, and let $n(u)$ be the number of vertices of the subtree $...
0
votes
0answers
43 views

Lower bounds on the length of circuits, depending on the number of times it crosses itself

I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below. Let $G(V,E)$ be ...
1
vote
0answers
47 views

Support of random closed walk in arbitrary graph

Researching a question related to closed walks on graphs, I have come across the following problem. Let $G$ be a connected graph on $n$ vertices and $k=O(\log(n))$. Pick a random closed walk on $G$ as ...
0
votes
0answers
16 views

Order-relational conditions for 4 points being in convex configuration

In the euclidean plane a simple sufficient condition for 4 points being in convex configuration is as follows: if the points are $\lbrace A,\,B,\,C,\,D\rbrace$ of which $\lbrace A,\,B,\,C\rbrace$ are ...
1
vote
0answers
38 views

Gromov-Hausdorff distance between graphs with edges as part of the space versus not part of the space

Let $G_1$ and $G_2$ be finite simple graphs viewed as metric spaces in the natural way where the edges are not part of the space. Let $G_1'$ and $G_2'$ be copies of $G_1$ and $G_2$ resp. but with the ...
0
votes
1answer
69 views

Value (not position)- based sorting; reference request

A recent answer of Ville Salo on the diameter of a Cayley graph induced by bubble sort generators (adjacent transpositions) has inspired this variation. Many sort algorithms are position based: you ...
0
votes
0answers
57 views

Expected number of directed cycle in a directed complete graph

Consider the randomized, directed complete graph G = (V, E) where for each pair of vertices u, v ∈ V, we add either the directed edge (u → v) or the directed edge (v → u) chosen uniformly at random. ...
1
vote
1answer
71 views

Outer automorphism group of $F(G)$

By a nice helpful comment in my last question, I see that if $\Phi(G)=1$ then ${\rm Out}(F(G))$($\cong G/F(G))$) is isomorphic to a direct product of ${\rm GL}(n_i,p_i)$. Actually, I’m digesting an ...
0
votes
0answers
37 views

Antimagic labelings to prove total coloring conjecture

An antimagic labeling of a simple graph with order $n$ and size $m$ is a surjective function from the set of edges to a set of labels (numbers) of size $m$ such that the sum of labels of the edges at ...
2
votes
0answers
40 views

Can a polytope with vertex-transitive edge graph or face lattice be made vertex-transitive?

Let $P\subset\Bbb R^d$ be a convex, full-dimensional polytope (convex hull of finitely many points, affine hull is the whole space), $G_P$ its edge graph and $\mathcal F_P$ its face lattice. Any of ...
1
vote
1answer
61 views

Distance pairs in labeled directed graph

Suppose we have a simple directed graph with $n$ nodes and $m$ edges, and we label each edge from $1$ to $m$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum ...
7
votes
1answer
297 views

Natural $\Pi_1$ sentence independent of PA

Order invariant graphs and finite incompleteness by Harvey Friedman gives an example of a combinatorial/non-metamathematical $\Pi_1$ sentence that is independent of ZFC. Is there a simpler example of ...
11
votes
2answers
563 views

Which curves and surfaces are realizable by linkages? references?

Ok, so I try to formulate rigorously the question in the title, for which I am asking for references. My definitions may be flawed, so feel free to adjust/correct them! I care about dimensions 2 and 3 ...
3
votes
1answer
74 views

Graph structure on $S_\omega$ induced by fixed points on compositions

Let $S_\omega$ denote the collection of bijections $f:\omega\to\omega$. We say that $f \in S_\omega$ has a fixed point if there is $x\in \omega$ with $f(x) = x$. It is a short exercise to show that ...
14
votes
2answers
457 views

A tree with prime vertices

Let us construct a simple (undirected) graph $T$ as follows: $\quad$ Let the set of all primes be the vertex set of $T$. For each prime $p$, take the least prime $q>p$ such that $2(p+1)-q$ is ...
4
votes
1answer
89 views

“Total rainbow” trees

Let $G= (V,E)$ be a simple finite graph which is (not necessarily properly) edge-colored. A rainbow spanning tree refers to a spanning tree T of G such that no color appears more than once amongst the ...
1
vote
0answers
24 views

Clustering number on ring lattice

I have seen in several places a useful formula that let us calculates the clustering number of regular ring lattice graphs with even degree but I have not found a convincing proof of it. Concretely, ...
8
votes
1answer
109 views

What graph's minimum vertex cover equals twice the maximum matching?

Matching: https://en.wikipedia.org/wiki/Matching_(graph_theory) Vertex Cover: https://en.wikipedia.org/wiki/Vertex_cover It is easy to see that $$\texttt{minimum vertex cover} \leq 2 \texttt{ ...

1
2 3 4 5
79