**2**

votes

**0**answers

8 views

### Graphs with prescribed numbers of k-cliques

Let $(a_0,a_1,\dots, a_n)$ be a sequence of non-negative integers.
Q. When does there exists a graph $G$ such that its number of $k$-cliques of $G$ is $a_k$ (that is $G$ has $a_0$ vertices, $a_1$ ...

**1**

vote

**0**answers

25 views

### Triange-free graph and its complement has Lovasz number > 3

I found an example by the method in the paper Explicit Ramsey graphs and orthonormal labelings by Noga Alon 1994. The graph is around $10^6$ vertices, anyone knows smaller graph which is Triangle-free ...

**-2**

votes

**0**answers

27 views

### Graph Isomorphism of Graphs that are not Locally Triangle-Free

What is the computational complexity of graph isomorphism problem for graph-class $\mathcal{G}$ that excludes graphs which are locally triangle-free ?
Is this $\mathcal{G}$ class included in any ...

**1**

vote

**3**answers

115 views

### Hadwiger number and minimal degree

Suppose $G$ is a finite simple graph and $\eta(G)$ is the maximal $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. If $\delta(G)$ is the minimal degree, do we have $\delta(G)\leq\eta(G)$?

**1**

vote

**0**answers

17 views

### History of the Vertex Disjoint Cycle Cover with Minimal Edgeweight Sum

Questions:
who first posed the problem of determining a collection of (directed) cycles, whose edgeweight sum is minimal and, for which each vertex belongs to exactly one of the cycles?
who came up ...

**-1**

votes

**1**answer

51 views

### Hadwiger number of total graph

Let $G=(V,E)$ be a finite, simple, undirected graph, and let $T(G)$ be its total graph. The Hadwiger number $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.
Is there an ...

**1**

vote

**1**answer

53 views

### Asymptotic formula for average geodesic length on graph?

If $G$ is a finite, connected simple graph then is there an expression for the average geodesic length?
That is suppose I know two nodes $n_1$ and $n_2$, the number of edges in my graph and at those ...

**-1**

votes

**1**answer

81 views

### Total chromatic number and total clique number

Let $G=(V,E)$ be a finite, simple, unconnected graph. We define the total graph $T(G)$ of $G$ as follows:
$V(T(G)) = (V\times\{0\}) \cup (E\times\{1\})$,
$E(T(G)) = E_v \cup E_e \cup E_{v+e}$, where
...

**0**

votes

**0**answers

35 views

### Generating tournaments inductively

This is a somewhat vague question, but I'm interested in ways to create a strong tournament from one or more smaller tournaments. Obviously, the disjoint union of two tournaments is a new tournament, ...

**-2**

votes

**0**answers

35 views

### Expected number of tree component should be less than equal to zero in random graph [closed]

In Erdos-Renyi random graph $G(n,p(n))$, set $p(n) ≥ (\frac{\ln n}{10n})$. We want to show that expected number of tree component on 11 vertices with this probability $p(n) ≥ (\frac{\ln n}{10n})$ ...

**1**

vote

**0**answers

64 views

### Zero-one law in binomial random graph model $G(n,p)$

Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has $\lim\limits_{n \rightarrow \infty} ...

**0**

votes

**0**answers

39 views

### Reconstructing a graph from set of sequences of edges

I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of ...

**-5**

votes

**0**answers

76 views

### Can any polynomial expressed as a chromatic polynomial? [closed]

Is it possible any polynomial with integer coefficients to be (or converted to) a chromatic polynomial that corresponds to a graph?

**0**

votes

**0**answers

16 views

### is any closed form relation that can state the error probability of code versus its variable and check node degree distributions?

In Low Density parity check code design, when bit (or frame) error probability of code is the objective of the design, we need a closed form relation between error probably (or even an approximate or ...

**0**

votes

**0**answers

53 views

### Binary operations on graphs

Are there "binary operations" on graphs like in (https://en.wikipedia.org/wiki/Graph_product), which make the set of all graphs ("under consideration")
a (abelian) group or
a (commutative) ring or
a ...

**1**

vote

**3**answers

198 views

### Existence of special graph

Let $G$ be a $n$-vertices graph and $\lambda_1$ is the largest eigenvalue of this graph. If $\lambda_1$ is an integer value, we can easily find the $\lambda_1$- regular graph with $n$ vertices. Now, ...

**2**

votes

**1**answer

32 views

### Edge-disjoint paths avoiding some subgraphs

Let $G$ be a directed graph on $n$ vertices. Let $H_1$, ..., $H_k$ be marked subgraphs of $G$. (Specifically, each $H_i$ consists of a subset of the vertices of $G$ and a subset of the edges of the ...

**2**

votes

**0**answers

58 views

### Number of $(2n-1)$-edge-colorings of the complete graph $K_{2n}$

I just started reading about graph theory and have a question (which might be trivial). How many $(2n-1)$ edge colorings of $K_{2n}$ are there?
A vaguer question: can I write $K_{4n}= K_4 + K_4 ...

**0**

votes

**0**answers

67 views

### Missing count in number of perfect matchings

Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be ...

**4**

votes

**1**answer

70 views

### Degree of neighbors in a simple graph (friendship paradox variant)

Context: this question is a translation of a common informal phrasing of the friendship paradox ("Most people have fewer friends than most of their friends"). Note that the question is similar to, but ...

**0**

votes

**1**answer

59 views

### Choosing directed subgraph in a triangulation

Consider triangulation $T.$
Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of ...

**3**

votes

**1**answer

58 views

### Maximal acyclic subgraph

It is well known that the problem of finding a maximal acyclic subgraph of a digraph is NP-complete.
Is this the case also when the digraph is symmetric ,i.e. if $(a,b)$ is a link, then $(b,a)$ is ...

**2**

votes

**0**answers

49 views

### Universal path function for all small trees

Let $f$ be a function $f: [k]^2 \rightarrow [k]$ (Where $[k]$ is the set $
\{0,1,\dots,k-1\}$).
A function $f$ is called $n$-universal path function if for every tree $T$ with $n$ vertices there ...

**0**

votes

**3**answers

99 views

### How to do a clockwise ordering of a planar graph in order to define its faces?

I am currently making an algorithm for planar graphs that I need to triangulate so they become maximally planar (that is triangulated and planar) given only the lists of neighbors for each node : no ...

**3**

votes

**2**answers

133 views

### Characterizing graphs whose Incidence Matrix has the all ones vector in its row span

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to known when the row span of ...

**3**

votes

**0**answers

31 views

### how to study the size of basins of attraction on a graph

I have a certain finite (but huge and without an apparent pattern, so that only numerical studies seem feasible) graph $G = (V,E)$, and a function $f: V \rightarrow \mathbb{R}$. On each edge $e = ...

**1**

vote

**0**answers

55 views

### bounded degree graph colouring.

I was wondering if anyone could provide references on the following:
Is determining the chromatic number of a bounded degree graph APX-complete?
2.I've seen the result that states it is NP-hard ...

**2**

votes

**0**answers

45 views

### Hypergraph edge colouring

I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...

**4**

votes

**1**answer

80 views

### Choice number of embedded graphs

For given $g$, consider the family of graphs which may be embedded to the compact orientable surface of genus $g$. For this family, consider maximal clique $\alpha(g)$, maximal chromatic number ...

**-3**

votes

**1**answer

64 views

### Connected homogeneous graphs [closed]

Let's call a simple, undirected graph $G=(V,E)$ homogeneous if for every $v,w\in V$ there is a graph isomorphism $\varphi:G\to G$ such that $\varphi(v)=w$.
It is clear that every finite homogeneous ...

**3**

votes

**1**answer

174 views

### A spectral graph theory problem

Let $S$ be a zero-free subset of the group ${\bf Z}_2^n$ and $\Gamma={\rm Cay}({\bf Z}_2^n,S)$ be a bipartite Cayley graph. For some choices of $S$, the graph $\Gamma$ has $4$ distinct eigenvalues, ...

**0**

votes

**1**answer

55 views

### Reference for Turan Density

I am working a 3-graph problem. I convert it to calculate Turan density, that is $lim_{n\to \infty}\frac{ex_3(n,F)}{\binom{n}{3}}$, where F is a3-graph. I'd like to know are there some methods and ...

**4**

votes

**1**answer

94 views

### Behaviour of eigenspaces of adjacency matrices after a single change to the graph

Say I know the eigenvalues and eigenvectors of an adjacency matrix of an unweighted graph. Can I say anything about the eigenvalues and eigenvectors of an adjacency matrix of a graph with one extra ...

**-3**

votes

**1**answer

51 views

### Hamiltonian path in countable connected graph such that $\text{deg}(v)=\omega$ for all $v$ [closed]

Is there a countable connected graph $G=(\omega, E)$ such that $\text{deg}(v)=\omega$ for all $v\in\omega$, but there is no Hamiltonian path in $G$?

**19**

votes

**3**answers

553 views

### Which paths in a graph are orthogonal to all cycles?

Start with some standard stuff. Suppose we have a directed graph $\Gamma$. I'll write $e : v \to w \,$ when $e$ is an edge going from the vertex $v$ to the vertex $w$. We get a vector space of ...

**3**

votes

**1**answer

101 views

### What is the densest bipartite graph with unique Hamiltonian cycle?

In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices.
Analogously, what is the ...

**1**

vote

**1**answer

131 views

### Number of eigenvalues of a Cayley graph

Let $G=Z_2^n$ and $S\subset G$. Is there any relation for number of distinct eigenvalues of $\Gamma=Cayley(G,S)$ graph depending on $n$ and $|S|$, or at least diameter of $\Gamma$? If you have any ...

**3**

votes

**1**answer

119 views

### Alternative parallel paths

There are $n$ non-intersecting strings (with ends $x_1,\dots, x_n$ and $y_1,\dots, y_n$). An additional string intersects the first $n$ strings somehow. All the intersections are simple (vertices of ...

**2**

votes

**1**answer

92 views

### Size of connected components of a graph via its spectrum

I know that we can determine the number of connected components of a graph from the eigenvalues of its Laplacian matrix. My question is:
Is there a way to understand the size of each connected ...

**7**

votes

**1**answer

283 views

### Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation.
Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$?
It is known that it is not always ...

**0**

votes

**2**answers

88 views

### Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ veritces and $M$ edges with 10 different colours in the whole graph. Each time I pass edges of different colour I have to pay additional fee equal to $K$. ...

**6**

votes

**1**answer

97 views

### Which graphs embedded in surfaces have symmetries acting transitively on vertex-edge flags?

A vertex-edge flag in a graph is a vertex together with an edge incident to that vertex. Given a graph $\Gamma$ embedded in a compact oriented surface $S$, when does the group of homeomorphisms of ...

**3**

votes

**1**answer

186 views

### Self-containing trees

Suppose that $r^2-r-1=0$ and that $T$ is the tree with root $1$ such that the children of each node $x$ are $rx$ and $x+1$. Remove all duplicates as they occur, and let $T(r)$ denote the remaining ...

**2**

votes

**0**answers

83 views

### Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph.
How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb ...

**1**

vote

**0**answers

77 views

### Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching of maximal cardinality. A tree is an acyclic connected graph.
Is there an efficient ...

**1**

vote

**0**answers

76 views

### maximal sets of vertices that avoids a clique

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...

**3**

votes

**1**answer

106 views

### chromatic polynomial of G - Join graph

Given a connected graph $G$ with $n$ vertices and given set of $\{m_1,m_2,...,m_n\}$ $n$ integers, we form a new graph $G^{\wedge} $ by considering the complete graph $K_{m_i}$ for each vertex i and ...

**-1**

votes

**1**answer

104 views

### Subgraphs of $\mathbb{R}^2$ in the Hadwiger-Nelson problem

In the setting of the Hadwiger-Nelson problem, two points of $\mathbb{R}^2$ form an edge if and only if their distance is $1$. The resulting graph $G$ has chromatic number $\chi(G)\in \{4,5,6,7\}$ and ...

**1**

vote

**1**answer

73 views

### Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.

**4**

votes

**1**answer

180 views

### exact definition of Fiedler vector

For a given N-vertex similarity graph $ G=(V,A) $ the eigenvalues of the unrenormalized (graph) Laplacian may be denoted as
$$ 0= \mu_0 \leq \mu_1 \leq ... \leq \mu_N $$
where the corresponding ...