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

learn more… | top users | synonyms

-3
votes
0answers
21 views

Calculate minimal number of nodes? [on hold]

Calculate minimal number of nodes? in a loopless simple undirected pi-partite graph. that has exacatly 144 nodes
-3
votes
0answers
24 views

Directed and undriected trees [on hold]

How many different directed trees can be obtained if we assign all possible orientation to the edges of an undirected tree having exactly 7 nodes? how many of them will be rooted(directed) trees?
0
votes
0answers
26 views

Determine number of directed trees and rooted trees obtainable [on hold]

I've been doing some exercices about graph theory and I find myself stuck on this one with no idea of to proceed. Here's the question : how many different directed trees can be obtained if we assign ...
0
votes
0answers
36 views

Is there such a thing as cyclic Hasse diagram for posets?

If so can you name one ? If not how to prove that there is none? Thanks !
2
votes
0answers
43 views

Maximal $k$-chordal subgraph

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges ...
1
vote
1answer
65 views

How to calculate the maximum number of rainbows for arbitrary graphs?

This question is inspired by problem 1 of the combinatorics test of the 2012 third round iranian olympiad which is as follows: We've colored edges of $K_n$ with $n-1$ colors. We call a vertex rainbow ...
2
votes
1answer
73 views

Distance between two networks

Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) ...
2
votes
0answers
59 views

Reconstructing a function from its variants that negate one argument

Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ...
5
votes
1answer
121 views

Integral straight-line embeddings of planar graphs

Wikipedia says (in the article on Fáry's theorem), "Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...
4
votes
1answer
85 views

Extremal graph theory for directed graphs

In extremal graph theory, there are results such as $$t(C_4,G)\geq t(K_2,G)^4,$$ where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...
-1
votes
0answers
29 views

departure time/overlap algorithm [closed]

i'm looking for "departure time/overlap algorithm" or any other idea. Suppose you have n trains and each one has a performance profile(how much electricity they need at the current time while driving ...
2
votes
1answer
59 views

Eigenvalues of a graph and its one-edge-delation graph

Let $G$ be any graph with at least one edge and let $e$ be any edge of $G$. Let $G-e$ denote the subgraph of $G$ obtained by deletion of the edge $e$. Assume that $G$ has $n$ vertices. Suppose ...
3
votes
1answer
79 views

A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not. The new problem is this. There is a tourist who has a having the following ...
0
votes
1answer
100 views

Spectral Graph Theory

Let G be an undirected graph, then Laplacian Matrix(L(G)) = Degree Matrix (D(G)) - Adjacency Matrix (A(G)). What is the relationship between laplacian and adjacency spectrum of undirected graphs?
0
votes
1answer
62 views

Laplacian matrix of a graph with negative weights

I am trying to calculate the Laplacian and Adjacency matrix of a graphs for positive and negative weights. If a graph be simple with only non-negative weight it is easier. But in my graph I have some ...
7
votes
4answers
286 views

Extremal examples for a folklore lemma on subgraphs of large minimum degree

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...
3
votes
0answers
117 views

Must distinct tree eigenvalues be relatively far apart?

How close to each other can two distinct eigenvalues of a tree be, as a function of the number $n$ of nodes ? For example, the path $P_n$ exhibits a gap of order $\frac{2\pi^2}{n^2}$ asymptotically ...
1
vote
0answers
28 views

Euclidean embedding of a graph based on 1-ring neighborhood distances only

Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...
4
votes
1answer
112 views

Graph presentation of Lexicographic shifts

Consider a finite alphabet $\{0,1, \ldots, n-1\}$. Let $\Sigma_n = \mathop{\prod}\limits_{j=1}^{\infty}\{0, \ldots n-1\}$ be the set of infinite one sided sequences and $\prec$ the lexicographic ...
1
vote
1answer
127 views

Degree Sequence Problem on $k$-Partite Graphs

The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees ...
0
votes
0answers
22 views

“Mutant knots” generalizable to “mutant tangled graphs”?

Just in case: Take a link L (drawn into the plane with over- and undercrossings), draw a closed loop C on it which cuts L in four points, rotate the inside of C around 180° (align the cut points on ...
5
votes
0answers
72 views

Implementations of Tutte polynomial [reference request, of a kind]

This question is not a 100% fit for MO, but it is a serious question that can be viewed as a sort of reference request, and I think fits here more than elsewhere. I have been asked to write a chapter ...
2
votes
1answer
219 views

Is there a graph with 99 vertices in which every edge belong to a unique triangle and every nonedge to a unique quadrilateral?

99-Graph:Is there a graph with 99 vertices in which every edge(i.e. pair of joined vertices) belong to a unique triangle and every nonedge(pair of unjoined vertices) to a unique quadrilateral?
2
votes
1answer
45 views

Graph construction to double coloring & Hadwiger number

For any graph $G$ let $\eta(G)$ be the Hadwiger number of $G$. Is there for every graph $G$ a graph $2G$ such that -- $\chi(2G) = 2\chi(G)$, and -- $\eta(2G) = 2\eta(G)$? For each one of the above ...
0
votes
1answer
54 views

Additivity of genus of a graph [duplicate]

Let $G$ be a finite simple undirected graph. Suppose there exist subgraph $G_1,G_2,\dots,G_n$ of $G$, such that $E(G_i)\cap E(G_j) = \emptyset$ and $|V(G_i)\cap V(G_j)| \leq 2$, for $i\neq j$. Then, ...
0
votes
0answers
133 views

Induced graphs of cayley graph

I have a Cayley graph $Cay(G,S)$, its group presentation $G=< S | R >$ and it is a metric graph by assigning a length equal to 1 to each edge. I also have an induced subgraph of that Cayley ...
1
vote
0answers
57 views

Recovering Spherical Harmonics from Discrete Samples

Consider a collection of $N$ points on the 2-sphere chosen uniformly at random. Let's say that there's an edge between two such vertices if their geodesic distance is less than $r_N$. The resulting ...
3
votes
2answers
119 views

Definition of the Moebius Ladder Graph

I found two different definitions of the Moebius Ladder Graph, whose essential difference is, whether the smallest one shall be $K_4$ or $K_{3,3}$. according to Wikipedia ...
0
votes
0answers
39 views

Preferential Attachment and salton similarity in directed networks

Preferential Attachment similarity between two nodes in an undirected graph is the degree of the first node multiplied by the degree of the second node. But what about directed graphs? Which degree ...
1
vote
1answer
65 views

Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language: $L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$. ($G$ ...
2
votes
2answers
113 views

Which graphs generate a matroidal independence complex?

The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$. Now, if $G$ is a well-covered graph (where all maximal ...
0
votes
0answers
40 views

Almost symmetric route in digraphs

Let $D=(V,E)$ be a digraph. A route of length $k$ in $D$ is a pair $L=(S,\sigma)$, where $S=(s_1,s_2,\dots,s_{k+1})$ is a sequence of $k+1$ elements of $V$, and ...
1
vote
0answers
56 views

Disconnecting a three regular graph

Setting, a random three regular graph. If I start removing edges, what's the probability that I disconnect it? What I know is that if I disconnect a graph I get a subgraph, and that the expected ...
14
votes
1answer
1k views

What have simplicial complexes ever done for graph theory?

(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...) Are there examples of results in "classical" [*] graph theory that have been achieved by using simplicial ...
7
votes
0answers
156 views

Genus of the graph $K_{4,2,2,2}$

I have ask this question in math.stackexchange, here. Since, there is no answer and apart from that i feel that the problem is difficult, i would like to ask it here. The problem is to find the genus ...
1
vote
1answer
99 views

The edge chromatic number and pefectness of inflation of cubic graph

The inflation of graph $G$ is a graph $I(G)$ which is obtained by replacing each vertex $x$ by a complete graph $K_{\deg(x)}$ and joining each edge to a different vertex of $K_{\deg(x)}$. Let $G$ ...
5
votes
1answer
167 views

Minimum Spanning Tree of Graph with Unknown Weights

I have a fully connected graph $G=(V,E)$ with $n$ vertices. The edge weights $w(e)$ with $e\in E$ are non-negative and form a metric space (e.g. Hamming distance), thus for vertices $v,u,y \in V$, we ...
4
votes
1answer
167 views

Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge. Note that the number of paths between two endpoints of a $k$-chain is $2^k.$ Question: Let ...
4
votes
2answers
167 views

Are the following Cayley digraphs Hamiltonian?

Consider the Cayley graphs $A'G_n$ on the alternating group $A_n$ with generating set $S = \{(1i2) : 3 \leq i \leq n\}$, for $n \geq 4$. See the following page on Alternating Group Graphs for ...
1
vote
0answers
103 views

Knight's metric: ellipse and parabola

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...
3
votes
0answers
48 views

Independence Number of K4-free planar graphs

The independence ratio is defined as the size of the maximum independent set divided by $n$. By the 4-color theorem, every planar graph with $n$ vertices has independence ratio at least $1/4$. ...
0
votes
0answers
36 views

labeling graph of positive weighted vertices

is there a polynomial solution for the below problem? is it similar to a known problem in graph theory? Given a directed graph G with cycles such that: • G has a start node s with a path to every ...
1
vote
1answer
74 views

Neighborhood overlap matrix for a bipartite graph

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap ...
9
votes
3answers
698 views

Could a perfect squared square be split into two perfect squared squares?

This is a geometric puzzle though it might conceivably also define a special class of Pythagorean triples. A perfect squared square PSS is a square (as a plane figure) partitioned into smaller ...
1
vote
1answer
116 views

Max order for which connected Cayley Graphs are known to be Hamiltonian

There is a well-known conjecture that all connected Cayley graphs are Hamiltonian. For how large a value of n has the conjecture been verified (i.e., for all groups whose order is at most n)?
2
votes
1answer
142 views

Does index 2 subgroup imply bipartite Cayley graph?

Let $G$ be a finitely generated group and let $\Gamma=Cay(G, S)$ be the Cayley graph of $G$ with respect to some generating set $S$. If there exists $S$ such that $\Gamma$ is bipartite, then $G$ has ...
1
vote
0answers
49 views

interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...
6
votes
1answer
142 views

Does high min degree and high odd girth imply near bipartiteness?

Say $G$ has odd girth at least $k$ and min degree $2n/k$. There is a classical result by Andrasfai, Erdos, and Sos that says that $G$ is bipartite. (Odd girth is the length of the shortest odd cycle ...
4
votes
4answers
311 views

Determine if a graph has a large clique

This question is quite specific and practical. I hope it is still relevant for MO and will not be removed. I have a collection $\mathcal{C}$ of graphs having from 5000-6000 vertices and edge density ...
1
vote
0answers
82 views

Motivations Needed: Paul Erdős Maximal Triangle-free Graphs

Among the collections of the open problems of Paul Erdős on the website of Professor Fan Chung, there is one called "number of triangle-free graphs". ...