Tagged Questions

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

28 views

58 views

Computing canonical forms from orbit partitions

Suppose we know the orbit partition of the vertices of a graph (due to the action of its automorphism group). Is it easy (as in "polynomial time") to generate a canonical form (aka "canonical labeling"...
48 views

Count Functional digraph [on hold]

Given a set of nodes, how can I count the number of different functional digraph containing a specific number of connected components? With a restriction that no node can have an edge point to itself. ...
24 views

On balanced bipartite graphs

Of the $2^{n^2}$ balanced bipartite graphs on $2n$ vertices how many of them have $i$ perfect matchings where $i\in\Bbb N\cup\{0\}$ and $0\leq i\leq n!$ holds?
1k views

Should axiomatic set theory be translated into graph theory?

Recently I saw the abstract of a paper by Nash-Williams: Should axiomatic set theory be translated into graph theory?''. The abstract, taken from Mathscinet says the following: The author ...
545 views

Bound on graph domination number when min degree is 7

I have a graph $G$ whose minimum vertex degree is $\delta=7$. I am seeking an upper bound on the domination number $\gamma(G)$ in terms of the number of vertices $n$ of $G$. I found a paper by Edwin ...
63 views

On some examples of critical families

I'm reading the book on Injective choice functions by Holz, Podewski and Steffens, and I find it to be at the same time well written and quite difficult. It has almost no examples - and in quite a few ...
548 views

97 views

Connection between PageRank and Fiedler vector

This question is on graph clustering. In its simplest form, the eigenvector corresponding to the second smallest eigenvalue of the normalized Laplacian of a graph provides a relaxed solution to the ...
191 views

Do right-profiles determine graphs up to isomorphism?

For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$. Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, ...
78 views

How to compute graph ideal or cut ideal of a graph?

Graph ideals are a special case of Stanley-Reisner ideal, explained in Combinatorial Commutative Algebra book by Sturmfels, and graph ideals here. Graph ideals are generated by the minimal paths while ...
243 views

minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...
450 views

How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs. A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...
59 views

Non-orientable genus of union of graphs

It is known that the orientable genus of union of two (disjoint) graphs is the sum of their genus. So, it is natural to ask What can be said about the non-orientable genus of union of two (disjoint) ...
81 views

Bounds for number of edges of a graph, given girth and number of vertices

In reading a paper, I came across an affirmation "a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges" In a previous question I asked in this site about it, I was reffered to a ...
174 views

Product and coproduct for bipartite graphs

Consider the category $BiGraph$ of bipartite graphs (vertices are named "places" and "transitions" like in Petri nets) and continous maps. A subgraph is named open iff it is place-bordered, and a map ...
84 views

Existence of a Connectivity Polynomial for a simple graph?

I try to find a polynomial for an arbitrary simple graph $G$ that tells whether the graph is connected or not. A graph is st-connected if you can find a path between a vertex $s$ and a vertex $t$ -- ...
116 views

Assigning random orientation to an edge in a regular graph

Given a simple regular graph of degree $d$ on $n$ vertices. Assume an ordering of vertices and assume all orientations of edges is from $i$ to $j$ if edges $ij$ exists and $i<j$. Pick $m$ random ...
338 views

Name for minimum size of a set of vertices S such that every other vertex has a neighbor in S

Given a (non-multi)graph $G$ let $N_G$ be the least number of nodes that must be colored (by a single color) such that every other node in $G$ shares an edge with at least one colored node. (I am only ...
57 views

Induced matchings in a bipartite graph with every matching having the same number of edges

Suppose $n,k$ are positive integers such that $k\mid n$. Consider a bipartite graph $H=(A,B,E)$ such that $|A|=|B|=n$ and the edge set $E$ consists of the union of $m(H)$ induced matchings with every ...
148 views

Does an expander remain an expander after removing few vertices and edges?

Consider a sequence of expander graphs ($G_n$); say $G_n$ has $n$ vertices. Remove $o(n)$ vertices (and the edges emanating from these vertices) and cut $o(n)$ edges. Call $G'_n$ the largest connected ...
176 views

edge graph reconstruction conjecture : set vs multi set

Why is the edge reconstruction conjecture stated with the deck defined as the multi set of graphs formed by deleting one edge? Can someone give an example of two graphs such that the edge deleted ...
323 views

Graph spectra and topology

This is a somewhat vague question, but I'm wondering if there has been any research into connections between the spectrum of a graph and some notion of the "topology" of that graph. To give an ...
53 views

Looking for source: Max num of edges of graph with given number of vertices and given girth

In a paper I am reading, the author states: "It is simple and well known that a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges" He says that a proof can be found on Extremal ...
150 views

Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...
148 views

How many edges can be added to two circles before the graph becomes Hamiltonian?

Start with two $n$-circles $(v_1\cdots v_n)$ and $(w_1\cdots w_n)$ of vertice sets $V$ and $W$, where $n\ge 5$. Add a number of vertex-disjoint edges between $V$ and $W$ (thus no chords) in a way ...
Definition Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) ...