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

5,165 questions
Filter by
Sorted by
Tagged with
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. ...
• 323
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?
32 views

• 145
1 vote
176 views

• 4,969
1 vote
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:/...
• 10.1k
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 ...
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 ...
• 1
1 vote
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 ...
• 12.7k
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 ...
• 2,027
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 ...
• 9
26 views

• 41
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 ...
• 181
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 ...
• 105
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 ...
• 101
1 vote
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 ...
• 111
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 ...
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$ ...
• 31
1 vote
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 ...
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$. ...
• 3,157
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 ...
• 1,305
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 ...
• 15.6k
152 views

1 vote
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\}$ ...
1 vote
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 ...