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
5 votes
2 answers
159 views

Independence number of configuration graph (consisting of all (2k-1)!! ways to partition {1,2,...,2k} into k pairs)

Let $k$ be a nonnegative integer. A configuration on $2k$ labeled points is simply a partition of the points into $k$ pairs, so for any set of $2k$ labeled points, there are $(2k-1)!!$ configurations. ...
atenao's user avatar
  • 323
0 votes
0 answers
47 views

Reference for packing property and König property

Can someone please suggest reference material to study about the packing property and König property of ideals and some examples?
Sowbarnika R's user avatar
0 votes
0 answers
32 views

Largest root of the Adjacency matrix of two graphs (comparison)

Let $G$ and $H$ be two graphs whose spectral radius (largest eigenvalue) of the adjacency matrix is the largest root of the following polynomial: $$P_G(x) = x^6-x^5-(2a-n+5)x^4+(2a-n+1)x^3+2(5a-3n+5)x^...
User8976's user avatar
  • 199
1 vote
0 answers
46 views

Necessary or sufficient conditions for the $k$-fold intersection to be empty in a covering with a "tree structure"

Consider a finite collection of $d$-dimensional balls $\mathfrak{B}=\{B_1,\ldots,B_n\}$ which cover a PL $d$-manifold $M$, i.e. $M=\bigcup_{i=1}^{n}B_i$. Suppose we want to compute the Euler ...
rab's user avatar
  • 159
7 votes
3 answers
471 views

Real-world examples of unweighted directed graphs

Social Networks, Internet Traffic, Citation Networks, Transportation Networks, and Biological Networks exemplify real-world instances of unweighted directed graphs. Within these domains, the Graph ...
ABB's user avatar
  • 3,992
0 votes
0 answers
26 views

A class of directed graph, when their minimal polynomial of the adjacency matrix matches the characteristic polynomial

We consider an unweighted directed simple graph, $G$, with a Hamiltonian cycle. Q. Assume that the adjacency matrix of $G$ is non-singular. Do the characteristic and minimal polynomials of the ...
ABB's user avatar
  • 3,992
1 vote
0 answers
69 views

Percolative process distribution not equivalent to coupon collector problem distribution

I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a ...
Cardstdani's user avatar
17 votes
1 answer
1k views

Can the Pythagorean Graph be finitely colored?

Define the Pythagorean Graph as having nodes $a,b\in \mathbb{N}_{\ge 3}$ and an edge $a\rightarrow b$ if and only if $a^2+b^2$ is a square. After much searching I found the example in the picture, ...
Yaakov Baruch's user avatar
0 votes
0 answers
27 views

Hamiltonian Circuit Counting and Classification Problem

the Problem Description background Consider an undirected complete graph $G_n$ with $n$ vertices, where if the numerical labels of each vertex are consecutive, then the edge weight between them is $1$,...
nevermind_15's user avatar
0 votes
0 answers
18 views

Differential-vertex-deletion equation for graph functions $f(x_1,...,x_n;G)$ on $n$ vertices

I encountered a function $f$ defined over a graph $G$ in my research which does not satisfy a deletion–contraction recurrence but an equation of the form $$\partial_k f(x_1,...,x_k,..x_n;G)=g(x_k, N_{...
Jens Fischer's user avatar
1 vote
2 answers
176 views

Topology of directed graph $G$ with non-singular adjacency matrix

Given a directed graph $G$ with non-singular adjacency matrix, Q. Is there a directed subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...
ABB's user avatar
  • 3,992
1 vote
0 answers
72 views

Szemeredi Regularity Lemma - Reasonable Bounds

Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...
ABIM's user avatar
  • 4,969
1 vote
0 answers
108 views

Vertex cleaving and edge contraction as graph morphisms

In some approaches to operads and properads, categories of trees and graphs are used as "indexing categories" for this structure (see, for instance, https://arxiv.org/abs/0902.1954 or https:/...
Jonathan Beardsley's user avatar
0 votes
0 answers
17 views

P-equitable graph partition

I am now conducting a research in regards to p equitable graph partition problem. I need to use LP techniques to kernelize this problem parametrized by vertex cover. In basic definition of such ...
Math_nerd's user avatar
0 votes
0 answers
32 views

How can I measure similarity between two graphs with identical topology but different edge weights

I have two graphs, G1 and G2, with exactly the same topology. Their only difference lies in the edge weights, which vary between 0 and 1. How can I measure the similarity between G1 and G2 under these ...
k99's user avatar
  • 1
1 vote
1 answer
47 views

Complexity of maximum weight-sum matching for cycle graphs

I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights. Question: What is the fastest way of calculating such a matching? Because of ...
Manfred Weis's user avatar
  • 12.7k
2 votes
0 answers
115 views

Alon Tarsi reaches its lower bound for complete multipartite graphs

Consider a complete multipartite graph $G$ with $k$ $(k\ge2)$ parts with equal number of vertices $n$, where $n$ is even. If $k=2$, it is a well known result that the Alon-Tarsi number (ATN)(The ...
vidyarthi's user avatar
  • 2,027
0 votes
0 answers
31 views

Eulerian Trail proof in Walk Through Combinatorics [migrated]

I'm struggling with the proof of Eulerian trail in walk through combinatorics. As you now, the theorem states that "A connected graph G has a closed Eulerian trail if and only if all vertices of ...
Ulaş's user avatar
  • 9
0 votes
0 answers
26 views

Does there exist a Graph Counting Lemma in the Cut density condition?

Background: In http://dx.doi.org/10.1016/j.ejc.2011.03.011 Lem9.3 Svante Janson proved that let $0<p<1$ and graphon $W$ with $\int W=p$, if for any subset $A\subseteq\left[0,1\right]$ it holds $\...
bc a's user avatar
  • 41
2 votes
0 answers
98 views

Structural description of a particular set motivated by graph reconstruction

$\DeclareMathOperator\Coh{Coh}\DeclareMathOperator\Sym{Sym}\DeclareMathOperator\Aut{Aut}$In this post, I asked a question regarding a particular function $\psi$ whose construction is motivated by the ...
Joseph Zambrano's user avatar
0 votes
0 answers
34 views

Does this "linear-approximated" version of Graph Counting Lemma hold?

Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...
bc a's user avatar
  • 41
0 votes
0 answers
36 views

Are there 4-connected planar non-hamilton multi-graphs?

Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...
L.C. Zhang's user avatar
  • 1,615
0 votes
0 answers
28 views

Set of enclosed convex polyhedra in a graph

Given a straight-line graph embedded in $\mathbb{R}^3$ with known vertex coordinates and edges and no edge intersections, is it possible to find all the enclosed convex polyhedra inside? If so, is ...
n1ps's user avatar
  • 1
1 vote
1 answer
132 views

Chromatic number of the insert-and-shift graph on $S_n$

Let $S_n$ be the collection of bijections $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. In an earlier question, the insert-and-shift graph structure was introduced on $S_n$ and the resulting graph is ...
Dominic van der Zypen's user avatar
0 votes
0 answers
29 views

Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?

Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 3n $ edges. Call the set of edges corresponding to an edge $uv$...
Hao S's user avatar
  • 181
4 votes
1 answer
281 views

A question related to "Locally Sidorenko" type problem

Let $F$ be a bipartite graph and $\delta_F=\delta(F)$ be a constant. Let $p\geq 0$ be a given constant. Let $W$ be a graphon with $\int W=p$ and for any $A,B\subseteq \left[0,1\right]$ with $|A|,|B|\...
bc a's user avatar
  • 41
2 votes
0 answers
83 views

"separators" for nonplanar graphs embedded in the plane

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an ...
Hao S's user avatar
  • 181
0 votes
1 answer
85 views

Homology of independence complex after removing a vertex

Let $G$ be a chordal graph, $I(G)$ be its independence complex, and $v \in V(G)$ be a simplicial vertex (that is, $v$'s neighborhood is a clique). Is there a way to relate the homology of $I(G)$ and ...
Will's user avatar
  • 105
0 votes
0 answers
34 views

Asymptotic bound on the number of simple connected graphs of bounded degree

I have posted this question on Mathematics, but unfortunately no luck so far. Let $\mathcal{G}$ be the family of simple connected graphs on $n$ vertices, where each graph has more than $m$ edges, and ...
Kuzja's user avatar
  • 101
1 vote
0 answers
53 views

A generalized/set hamiltonian cycle problem on directed graphs

So this problem originally stems from the asymmetric generalized/set TSP problem, where I am interested in asking the question which or how many edges I can delete while maintaining feasability. The ...
whiterock's user avatar
  • 111
0 votes
0 answers
17 views

Bound the $\infty$-norm of the eigenvector of the second minimum eigenvalue of normalized Laplacian from below

I meet the above problem while reading a paper. The problem can be stated as below. Consider an undirected graph $G$. Let $\mathbf{v}$ be a vector such that $\mathbf{D}^{1/2}\mathbf{v}$ is the ...
Lasting Howling's user avatar
3 votes
1 answer
240 views

Why do we get a connected 2-regular graph?

In reading "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES" by Rostovtsev and Stolbunov, they claim on page 8 that the set $U=\{E_i(\mathbb{F}_p)\}$ of elliptic curves with a specific prime $l$ ...
Shean's user avatar
  • 31
1 vote
0 answers
42 views

If $G$ is a connected bipartite graph, then the edge ideal $I(G)$ is normally torsion free

I am studying the paper "On the Ideal Theory of Graphs" by Simis, Vasconcelos and Villarreal, Journal of Algebra 167, No. 2, 389-416 (1994), MR1283294, Zbl 0816.13003. I got stuck at theorem ...
Sowbarnika R's user avatar
2 votes
1 answer
144 views

Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?

Consider a simple hyperplane arrangement $H_1,\cdots,H_n$ in the Euclidean space $\mathbb{R}^d$. By "simple" we mean any $k$ hyperplanes in $\{H_1,\cdots,H_n\}$ intersect in codimension $k$. ...
YHBKJ's user avatar
  • 3,157
0 votes
2 answers
79 views

Isometric path cover number of the 2 dimensional grid graph

I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...
Pritam Majumder's user avatar
5 votes
0 answers
121 views

If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?

Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...
Per Alexandersson's user avatar
6 votes
1 answer
152 views

Approximating distance on a finite graph with Hamming distance

For this question, all graphs are understood to be finite, simple, and undirected. The distance metric on a graph $G$ means the length of the shortest path between the given vertices, i.e., for $v_1, ...
David Gao's user avatar
  • 1,262
3 votes
1 answer
55 views

Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?

I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...
Siddhu Neehal's user avatar
3 votes
0 answers
104 views

Finite approximability of graphs with finitely many automorphisms

In this question, all graphs are understood to be simple and undirected, and have countably many vertices and edges, but not necessarily finite. Let $G = (V, E)$ be a graph. It is clear that any ...
David Gao's user avatar
  • 1,262
4 votes
0 answers
219 views

Optimal colorings

If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$. For any coloring $c:V(G) \...
Dominic van der Zypen's user avatar
1 vote
3 answers
168 views

Graph on $\mathbb{N}$ where almost every vertex is shy

The following question is loosely based on the friendship paradox. Let $G=(V,E)$ be a simple, undirected graph. For $v\in V$, we let the neighborhood of $v$ be $N(v) = \big\{w\in V:\{v,w\}\in E\big\}$ ...
Dominic van der Zypen's user avatar
1 vote
1 answer
32 views

Homomorphisms relationship with Graph Degeneracy

Let $H, G$ be finite undirected graphs. We say that $H$ is $r$-degenerate if there exists an ordering of the vertices of $H$ such that the back degree of every vertex is at most $r$. This is ...
Sean Longbrake's user avatar
0 votes
0 answers
64 views

What is the complexity of computing isomorphism of two non-regular graphs?

Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...
Eauriel's user avatar
5 votes
1 answer
190 views

Chromatic number of the infinite Erdős–Hajnal shift-graph

For any set $X$, let $[X]^2= \big\{\{x,y\}: x\neq y \in X\big\}$. Let $\kappa$ be an infinite cardinal. Let $G_\kappa = ([\kappa]^2, E_\kappa)$ where $E_\kappa = \big\{\{a,b\}\in \big[[\kappa]^2\big]^...
Dominic van der Zypen's user avatar
4 votes
1 answer
204 views

Double cover the edges of a complete graph by smaller complete graphs

Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly ...
Wallace Rin's user avatar
3 votes
1 answer
114 views

Chromatic number of triangle-free graph $[[n]]^2$ with edges of form $a<b, b<c$

I am reading (and enjoying!) Bela Bollobas' book "Modern Graph Theory", and one of the exercises shows how to construct triangle-free graphs with large chromatic number: For any non-negative ...
Dominic van der Zypen's user avatar
1 vote
2 answers
416 views

What is the proper name for this "tersest path" problem in Infinite Craft?

The web game Infinite Craft gives you a starting set of elements $V_0\subset V$ and a mapping $E$ of type $V\times V\rightarrow V$. In fact, $F$ is commutative: $E(v_a,v_b) = E(v_b,v_a)$. So another ...
Quuxplusone's user avatar
3 votes
1 answer
191 views

Some questions about induced subgraphs of the directed hypercube graph

Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
Agile_Eagle's user avatar
3 votes
2 answers
109 views

Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?

For a graph of genus $g$, it holds that it cannot have too many disjoint 5-cliques, as each clique requires a new handle. It feels that given a graph of genus $g$, it cannot have an unbounded number ...
master bob's user avatar
1 vote
1 answer
103 views

A reliable reference for the statement every $k$-tree is uniquely $(k + 1)$-colorable

I see that every $k$-tree is uniquely $(k + 1)$-colorable in Uniquely_colorable_graph. Wikipedia does not cite any references, even though I know that its proof is not difficult by using mathematical ...
L.C. Zhang's user avatar
  • 1,615

1
2 3 4 5
104