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

4
votes
1answer
9 views

Analysis of the Laplacian of a random bipartite graph

My analysis of an engineering problem reduced to analysis of the Laplacian of a (random) bipartite graph. There are a few particular questions I am interested in, but not sure which direction to take ...
0
votes
1answer
201 views

Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$). The cost to send $x$ unit of flow through edge $e_i$ is defined ...
2
votes
0answers
83 views

Partitioning graph for Graph Isomorphism

Motivation: I am studying graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases required to get solution of graph isomorphism. Construction: $G$ is a $r$ ...
0
votes
0answers
68 views

Graphs from which two vertices can be exchanged

A graph is vertex transitive if $x \mapsto y$ by an automorphism. Let $P$ denote the stronger property that $x \mapsto y \mapsto x$ by an automorphism. Simple facts: $P \rightarrow$ unimodular. ...
0
votes
1answer
88 views

Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...
0
votes
0answers
42 views

Crossing all boundaries on a map? [on hold]

In a variation on the traveling salesman problem, is there an algorithm (an approximate heuristic is fine) that finds a short, if not the shortest, path that crosses all boundaries between each pair ...
8
votes
2answers
678 views
+300

A question on representation of graphs

Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...
1
vote
1answer
337 views

Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition

Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected. The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...
0
votes
0answers
63 views

A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...
0
votes
0answers
36 views

Counting the k-factors of the complete graph on n vertices [on hold]

I was originally trying to solve the following problem: 10 people are in a room, and you give them a task. Their task is for each person to shake hands with exactly 3 other people in the room. How ...
2
votes
2answers
52 views

Minimal edge color on constraints

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every even simple cycle contains an odd number ($>1$) of colors much larger than $(\log n)^\beta$ or ...
2
votes
0answers
49 views

Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...
4
votes
0answers
77 views

Does squaring a directed random graph more than double its out-degree?

As far as I know, it is an unsolved question whether or not this is true: If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least double that of its ...
1
vote
0answers
218 views

Incidence geometry and matrices

Supposing I have a $0/1$ or $\pm1$ matrix $A$ of size $m\times n$, is there a minimum $d$ (that works for every $m\times n$ $A$) such that there exists $m$ lines $r_1,\dots,r_m$, $n$ lines ...
1
vote
0answers
74 views

Efficiently counting all paths of length n in a graph with vertex visitation contraints [closed]

I have a graph G with two classes of vertices. The first class represents no resource limitation entities and can be visited an unlimited number of times in any path traversal. The second class of ...
0
votes
1answer
182 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
8
votes
2answers
225 views

Dividing the edges and diagonals of a polygon among disjoint sub-polygons

Let $P$ be a convex $n$-gon ($n$ is odd and $n \geq 5$). Determine the smallest $m$ such that all edges and diagonals of $P$ can be covered by the edges of $m$ convex sub-polygons of $P$ which ...
2
votes
2answers
127 views

“Nice” and “nasty” partitions in graphs

Let $G=(V,E)$ be a simple, undirected graph, that is $V$ is a set and $E \subseteq [V]^2 = \{\{v,w\}: v,w \in V \land v\neq w\}$. For $v\in V$ and $S\subseteq V$ we set $$N(v,S) = \{w\in S: \{v,w\} ...
5
votes
1answer
142 views

Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...
1
vote
0answers
28 views

One sided Satisfactory Partition problem

The Satisfaction Partition problem is to decide if a graph has a vertex partition (U,V) into non empty parts where each vertex has as many neighbours in its part as in the other part. This problem is ...
1
vote
2answers
107 views

Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties: The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it). $T$ has a ...
3
votes
1answer
153 views

Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...
5
votes
0answers
168 views

Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...
1
vote
0answers
33 views

Weak law for component count of Erdos-Renyi random graphs

Penrose and Yukich derive a weak law for functionals of binomial point processes, which implies a law of large numbers for the component count of random geometric graphs. Do similar results exist for ...
1
vote
0answers
94 views

From Planar Graphs To Tangent Circles

I have a conjecture: "For each planar graph with vertices $V_1, V_2,\ldots, V_n$ there exist disjoint circles $w_1,w_2,\ldots,w_n$ in the plane, such that for every $i,j$, $w_i$ is tangent to $w_j$ ...
6
votes
1answer
345 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 ≥ ...
2
votes
1answer
59 views

Images of interval edge coloring

I found out the definition of interval edge colorings, concept put by Kamalian in various papers but could not find a graph depicting an example. Where can I find pictures of explicit examples of ...
8
votes
1answer
196 views

Smallest strongly regular graph whose automorphism group is not vertex transitive?

I'm looking for a small strongly regular graph whose automorphism group is not vertex-transitive. This answer to a different question shows that the Chang graphs on 28 vertices are such graphs. Is ...
12
votes
1answer
434 views

Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly $$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor ...
12
votes
1answer
148 views

Reconstruction Conjecture: are almost all digraphs reconstructible?

The Reconstruction Conjecture for simple graphs remains unresolved. Most attempts I've seen at resolving the conjecture aim at proving it to be true (or partially true). I don't believe there is a ...
0
votes
1answer
97 views

Petersen 2-factor decomposition theorem for directed graphs

Petersen proved that every 2k-regular graph can be decomposed into k disjoint 2-factors. I would like to know that is it true that if G is a directed regular graph (d_out(v)=d_in(v)=k), then can G be ...
1
vote
0answers
109 views

Cayley graphs with special subgraphs and some related problems

I asked some questions about finite Cayley graphs with special type of subgraphs which has been answered by Dear Prof. Godsil. It can be seen in the MO page with address: Cayley graphs and its ...
0
votes
1answer
103 views

Two graph structures on $\text{Hom}(G,H)$

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq [V]^2 := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, ...
1
vote
0answers
55 views

Interpreting (Fiedler) spectral bisectioning

I would appreciate help on how to interpret the results of spectral bisectioning of a graph. Given a $G=(V,E)$ with size $N$ represented by $Q$ its Laplacian matrix where the eigenvalues are ordered ...
0
votes
2answers
112 views

Generate all non-isomorphic partitions $\pi = \{ \{1, …, n-1\}, \{n\} \}$ for all graphs of order $n$

Let $G$ be any connected, undirected, and unweighted graph of order $n$. Let $\pi = \{ \{ 1, ..., n-1 \}, \{ n \} \}$ be partitioning of $G$ such that always $n-1$ vertices are in the first cluster ...
12
votes
1answer
864 views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...
19
votes
5answers
2k views

The Matrix-Tree Theorem without the matrix

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me ...
5
votes
1answer
81 views

Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity? Especially modeling ...
20
votes
1answer
247 views

A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph? I'd like to avoid exhaustive ...
4
votes
0answers
45 views

Existence of certain graph gadget related to coloring odd hole free graph

Wondering about the existence of graph gadget related to coloring (or 3-coloring) odd hole free graphs. Let $G$ be simple $k$-chromatic connected graph with two vertices $u,v$. Is it possible $G$ to ...
1
vote
0answers
138 views

Complexity of reordering a matrix which consists independent sub matrices

Introduction: Given a matrix A of a $k$ regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ is the symmetric matrix of the graph $(G-x)$, ...
3
votes
1answer
156 views

“Canonical” graph structure on $\text{Hom}(G, H)$

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq [V]^2 := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, ...
8
votes
2answers
343 views

Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$). For odd integers $n$ we have $n=\chi(K_n) = ...
4
votes
0answers
141 views

What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
2
votes
0answers
42 views

Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...
0
votes
0answers
42 views

Enumeration of simple graphs with given degree distribution/sequence [duplicate]

Is there any exact formula for asymptotic/exact enumeration of simple graphs with given degree sequence? I just found some results about it, but the formula is hold on for some conditions, for example ...
1
vote
0answers
105 views

What are constructions for induced $C_5$-free graphs?

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, ...
13
votes
1answer
877 views

How many labelled disconnected simple graphs have n vertices and floor((n choose 2)/2) edges?

I would like to know the asymptotic number of labelled disconnected (simple) graphs with n vertices and $\lfloor \frac 12{n\choose 2}\rfloor$ edges.
1
vote
0answers
29 views

Small degree vertices in an epsilon-tough graph

We say that a graph is t-tough if by deleting a set if vertices $S$, the resulting graph will have at most $|S|/t$ connected components. We say that a graph is minimally t-tough if the deletion of an ...
4
votes
0answers
86 views

Prove or disprove a claim about covering a polytope by convex polytopes in a certain way

Here is the claim: Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes ...