1
vote
0answers
19 views

Decomposing the Complete Graph into Forests

Which spanning forests can we partition the complete graph $K_n$ into? I am primarily interested in partitions into one fixed isomorphism class of forest. I'm also assuming whatever divisibility ...
1
vote
0answers
22 views

Transforming spanning sub-graphs

I have the following question: Suppose we have a finite graph $G=(V,E)$. Now take two arbitrary spanning sub-graphs, i.e. $G_1 = (V,E_1)$ and $G_2=(V,E_2)$ with $E_1,E_2 \subseteq E$. Suppose we ...
1
vote
0answers
38 views

A combinatorial enumeration problem on graph

Let $G$ be a complete graph of order $n$, we now delete $i$ edges from it, then how many complete subgraphs are there with order $m$ in the rest graph? (You can assume $m\ll n$ and $i\ll m$ if ...
1
vote
1answer
21 views

Graph with small average degree has two vertices of small degree

Suppose $G$ is a graph and its average degree $\epsilon(G) = \frac{2|E(G)|}{|V(G)|}$ is in the interval $0 < \epsilon(G) < 2.$ Then clearly $G$ has one vertex of degree at most $1.$ Reading ...
2
votes
0answers
19 views

Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
0
votes
0answers
50 views

Kempe chain color swaps in a partially colored map

Crossposted to: http://mathoverflow.net/questions/179340/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using only Kempe chain color swaps (as ...
1
vote
1answer
33 views

proof of Konig's Theorem for bipartite graphs from Menger's Theorem

Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem? Konig's Theorem is as follows: For a bipartite graph $G$, the maximum size ...
-1
votes
1answer
47 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
1
vote
0answers
18 views

Gallai & Milgram path covers theorem from Diestel

I have a question about the theorem of Gallai and Milgram stating that every directed graph has a path cover $P$ such that one can make an independent set of $G$ by picking vertices from each of the ...
1
vote
0answers
16 views

How many graphs on n nodes, with each component a coherently directed tree

For a positive integer $n$ choose $m$ with $1 \le m \le n$ and let $X$ be a set with $|X|=n$. choose $x_j \in X$ for $j=1,...,m$. Define $m$ directed graphs $X_j$ in the following way: Initially we ...
1
vote
1answer
58 views

counting full bipartite matchings

My actual question is to find the number of transversal given a collection of set ... After a little bit of study it has come down to: How can we count the number of matchings in a bipartite graph ...
3
votes
0answers
40 views

Prove that the number of nonisomorphic ways to partition $E(k_n)$ into complete bipartite graphs at least $2^{n-4}$

Apparently the solution is exercise 1.4.5 in Babal and Frankl's "linear algebra methods in combinatorics (1992)" but it seems they never actually got around to publishing this. Or at least, I am ...
0
votes
0answers
19 views

Number of Strongly Connected Components and Property Testing.

I am working on a problem about the strong connectivity of digraphs. Given graph $\vec G$ that is $k$-$\textit far$ away from being strongly connected (i.e, the minimum number of edges that need to be ...
0
votes
0answers
51 views

Is this composition of $K_{4,4}$ graphs minor-closed?

Following graph is a composition of $K_{4,4}$ bipartite graphs with all the edges are of same length. How do I know whether it is minor-closed or not? The definition in the Wikipedia is as follows. ...
0
votes
0answers
33 views

Number of unique ways to edge-label a complete graph with $k$ distinct labels.

Given $k$ distinct labels, how many unique ways to label the edges of a complete graph with $n$ nodes (nodes are not labeled). For example, to label a complete graph with 3 nodes using 4 distinct ...
1
vote
1answer
31 views

Diameter of a 2-Lift of complete bipartite graph

Give an undirected simple graph $G$ with $n$ vertices and $m$ edges, its 2-Lift is constructed as follows: Define $G_1$ to be the original graph $G$. Make a duplicate copy of $G$ and call it $G_2$. ...
0
votes
1answer
256 views

proof of a theorem in a paper

I was reading a paper named Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths by P. K. Jha (Indian J. pure appl. Math. 23(8): 585-606, August 1992). In one ...
1
vote
0answers
19 views

minimum number of unit distances required for a unit equilateral triangle

Problem. Suppose we have $n$ points on the plane. Among $\binom{n}{2}$ pairwise distances, there are $e$ number of unit distances. Find minimum $e$ ($e$ as a function of $n$) so that there is a ...
1
vote
0answers
32 views

Probability that a subset of a degree-regular graph shares at least a certain number of mutual connections

Consider a set of $n$ vertices of common degree $p$. What is the probability that some subset of $x$ vertices from $n$ share $q$ mutual connections within that group of size $x$? i.e. If we have ...
6
votes
0answers
123 views

Parity of sum of Kronecker deltas in a graph

For some fixed $n\in\mathbb N$ let $G$ be a graph on the vertex set $\{1,\dots,n\}$ with a total number of $k$ edges $e_1,\dots, e_k$. For any vertex colouring $c(i)$ of the graph, $\delta_e$ is ...
9
votes
1answer
142 views

Graph partition that span a third of edges

Given a graph G is easy to see that we have a partition $V=V_1 \cup V_2$ so that $$e(G[V_1])+e(G[V_2])\leq e(G)/2$$. How can we improve this result showing that we can choose $V_i$ such that ...
0
votes
2answers
28 views

How to find a pointset with unique distances

Is there a way to arrange N number of 2D points within a box so that the distances between the points are unique? I have an application where I can measure the distances between points with some ...
2
votes
1answer
18 views

Eccentricity of vertices in a graph when eccentricity of one vertex is given

I have a very basic doubt. If a vertex in any graph has the eccentricity two, then what can be concluded about eccentricities of other vertices in graph. Is the eccentricity of every vertex is less ...
2
votes
0answers
31 views

Counting symmetric binary matrices with constant line-sum

I'm trying to count, as the title suggests, symmetric matrices with entries $0$ or $1$ and constant line-sum $k$. ($0 \leq k \leq n$). If you start listing the number of these on a table you'll get a ...
2
votes
1answer
44 views

Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
7
votes
1answer
83 views

The rows continue to be different to each other

In each position of an $n \times n$ matrix there is a number. We know that all the rows of the matrix are different from each other. Show that we can delete a column so that the rows of the matrix ...
1
vote
1answer
43 views

Examples of Matroids

Preparing an exam, I'm looking for examples of matroids and maybe hints or references on proves that they are. (what I already know are representable matroids and graphic matroids)
4
votes
1answer
38 views

Chromatic number of generalized hypercube

It's clear that the chromatic number of $Q_n$ is $2$. But what about the graph $G$ with vertex set ${n}^{(r)}$ where two vertices are adjacent if and only if their coordiantes differ by one? Can't ...
6
votes
1answer
47 views

Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
1
vote
0answers
69 views

Research Topics Needed

This coming academic year a professor has asked me to find some topics that I wish to pursue to write about. The problem/topic that will be discussed doesn't have to be open, but my trouble is that I ...
5
votes
2answers
92 views

Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)? The obvious necessary conditions work: $K_{12,12}$ ...
1
vote
0answers
27 views

Round robin tournament scheduling with additional constraints

I'm looking for a solution to the following problem. Given $n = a\cdot (b-1) + 1$ players, $a$ and $b$ being integers with $a \leq b$, I want to schedule a round-robin tournament where every player ...
4
votes
1answer
49 views

All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
0
votes
1answer
18 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
2
votes
1answer
45 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
1
vote
0answers
24 views

A inequality on a graph and finding the best constant

Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The ...
3
votes
0answers
48 views

What is the number of labeled caterpillars?

A caterpillar is a tree in which all the vertices are within a distance 1 of a central path. (See the Wikipedia article: Caterpillar tree, for an example and some equivalent characterizations). The ...
0
votes
0answers
21 views

Threshold function for component of size $k$

Show that, for each fixed $k$, there is a function $p(n)$ such that the probability that $G(n,p(n))$ has a component of size exactly $k$ tends to $1$ as $n \rightarrow \infty$. My initial thoughts are ...
1
vote
0answers
36 views

Variations of M,n,k-games

I just read about M,n,k-games and wondered if the following variation (with fixed $k$) has been studied as well and if there exists a name for it: Two players consecutively mark elements of ${\bf Z}$ ...
0
votes
1answer
15 views

Differnce between circuits in graphs

Given a full undirected graph with 3 vertices: $v1, v2, v3$ and $3$ edges. Is there any differnce between those 2 cycles: $C1: v1-{(e1)}-v2-{(e2)}-v3-{(e3)}-v1$ $C2: ...
2
votes
0answers
31 views

Probability that half the nodes has more than half out-degree

This is something I just wondered about, and I don't know whether there is a closed-form answer or not. I've tried but without making progress, so any idea would be helpful. Consider a complete graph ...
1
vote
0answers
31 views

resilience of graphs question

The following is a definition of the resilience of a graph w.r.t to a property $\mathcal{P}$ (Local resilience) A property $\mathcal{P}$ is said to be monotone if the property is preserved under ...
0
votes
1answer
33 views

Distance Transitive Graph Property

Asked this over in math overflow and have refined the question a bit. I'm working on trying to show this, but can't seem to get a proof methodology worked out. No guarantees that it is true, but ...
0
votes
0answers
58 views

2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
2
votes
3answers
245 views

Combinatorial optimization - Bijections between duplicated numbers

English is not my native language: sorry for my mistakes. Thank you in advance for your answers. Two Bijections and an Array... Here is a 2D array (in this particular example: rows: 1 to 4; ...
0
votes
1answer
26 views

Distinguishing between two sets of tournament partition

A "tournament" is a complete graph such that each edge is directed one way or the other (but not both). Does there exist a tournament of size $2n$ such that we can partition it into two sets $A,B$, ...
0
votes
0answers
19 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
1
vote
2answers
52 views

Prove that a complement graph of a tree is either connected or it's a union of an isolated vertex and a full graph

I managed to prove the second part - that a tree that is one vertex with n-1 degree and all the rest are connected to it - the complement graph of such tree is an isolated vertex and the rest of the ...
0
votes
1answer
25 views

No minimal imperfect graph of order 200

Prove that there is no minimal imperfect graph of order 200, without using the Strong Perfect Graph Theorem.
2
votes
1answer
40 views

What is the realization of a graph in $\mathbb{R}^d$?

I am an undergraduate who has been overhearing students talking about realizations of graphs in $\mathbb{R}^d$, and I am curious to know what that means. To be honest, I don't even know what a ...