# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

27 views

### The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the ...
44 views

### Finding the longest path in a directed graph where each node can be visited $N$ times?

I've read that the longest path problem is $NP$-Hard, but what about where it is specified that each node can be visited a maximum of $N$ times? It seems the longest-path problem is a special case of ...
33 views

### Is class of graphs with eigenvalue $1$ of any particular importance?

Are graphs with eigenvalue $1$ of multiplicity more than $1$, important one? Please guide me to any book or article discussing such graphs.
24 views

### Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
28 views

### references of discrete association scheme

I tried to find a book or paper to understanding discrete association scheme but I could not get any book for that. What is the good references for that?
63 views

### Is it always possible to get MC/DC coverage on an $n$-input Boolean function with $n + 1$ test cases?

In software engineering, there is a coverage metric for testing called modified condition/decision coverage, or MC/DC for short. This metric is well-known in the avionics industry due to showing up in ...
30 views

### Show that any vertex $v$ of $P$ is half-integral.

Let $G$ be an undirected graph and define $$P=\{x \in R^{V}: x(u)+x(v) \leq 1 \:\:\text{for all edges}\:\: e=uv,\:\: x \geq 0\}$$ Show that any vertex $v$ of $P$ is half integral.
23 views

### Bipartite graphs whose minimal cycles have length $4$

Is there some literature about bipartite graphs whose minimal cycles all have length $4$? By that I mean that any cycle in the graph with length strictly greater than four can be divided into cycles ...
37 views

### Small graphs containing all trees on $n$ vertices

What do those graphs look like which contain a copy of every tree on $n$ vertices and such that no proper subgraph has this property?
51 views

### Graphs of (un)bounded color valence

Talking about colored graphs there is a definition given for graphs with bounded color valence. This definition is as follows: A vertex-colored graph $G=(V,E)$ has bounded color valence, if there ...
21 views

### Number of global min cuts in undirected graph

I'm looking at a proof of the following theorem "The number of global minimum cut is $\le \binom{n}{2}$". It says $\forall i$ from $1$ to $n-1$ Find min-cut seperating $\{1,2,\cdots,i\}$ from $i+1$. ...
36 views

41 views

### Supply/demand digraph - understanding problem

I'm dealing with multiflows and I found in "Combinatorial Optimization - Part C" by Schrijver in Chapter 70 a good source. The definition of the multiflow problem involves so-called supply- and demand-...
59 views

### Number of Hamilton paths in an extremely dense undirected simple graph

What is the fastest way (algorithm) to calculate the number of Hamilton paths in an extremely dense undirected simple graph (approximately 99.99% edges are connected)? I was thinking of the following ...
25 views

### Why is the eigenvector centrality considered a generalized version of degree centrality?

The eigenvector centrality of a vertex in a graph, is a self-referential centrality, which basically says that a vertex with a high value of eigenvector centrality is one that is adjacent to highly ...
35 views

### $K_3$ subgraph in a random graph

Consider a random graph of $n$ vertices where the probability of there being an edge between any two vertices is .01. I want to see what is the asymptotic behavior of the probability that ...
92 views

### Number of different Graphs with n vertices

A graph has 7 vertices and 7 edges. How many different graphs (non- isomorphic) are possible? The resulting graph has no constraints. i.e. it can be either connected or disconnected graph. How can I ...
37 views

225 views

### A planar graph $G$ is the dual of its dual if and only if $G$ is connected.

That is, prove that a planar graph is the dual of it's dual iff it is connected. I know that in order for this to be true, G must be isomorphic to it's dual (G'), but I'm not sure how connectedness ...
31 views

### Concrete solution to the (oriented) Oberwolfach problem with one table

The oriented Oberwolfach problem (with only one table) and its solution are the following. In a meeting of $n$ people during $n-1$ days (combinatorists at Oberwolfach for concreteness), they all have ...
I'm trying to prove that if $G$ is bi-partite and $d$-regular for $d \geq 1,$ then $G$ has a one-to-one and onto matching between the two partitions of the graph. I have a feeling that I need to use ...
### Finding the exact value for $H(7)$
The graphs that I work with are all complete, each edge is colored red or blue, and each vertex is colored red or blue. $\textbf{Definition:}$ A graph is $\textit{Happy}$ if there exists a vertex ...