-1
votes
2answers
49 views

number of edges in a graph

I got a problem related to graph theory - Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is {(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, ...
5
votes
0answers
36 views

Union of 2 expander graphs [closed]

Suppose that $G$ and $H$ are both expander graphs on the same node set with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$. What can be said about the expansion of graph $G \cup H$? In ...
4
votes
1answer
107 views

What is average number of cycles in an undirected ordered graph of size n?

What is average number of cycles in an undirected ordered graph of size $n$? I've tried finding out sum of number of cycles in all sorts of a graph of size n but I couldn't find that out.
1
vote
2answers
86 views

Calculate number of ways to color matrix using inclusion-exclusion principle

This was asked in a recent contest. The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same ...
3
votes
3answers
273 views

Number of ways to fill a 2xN grid with M colors

This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two ...
4
votes
2answers
117 views

Bipartite Graph Game

So say we have a bipartite graph G=(X,Y,E). Let's make a game out of it. I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it's ...
3
votes
1answer
53 views

Unranking paths in a graph/lattice

A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified ...
4
votes
1answer
168 views

Simple graph canonization algorithm

I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if ...
6
votes
1answer
251 views

Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph

Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes. I tried to look it up at a few places (including ...
1
vote
1answer
131 views

Number of Combinations of Connected Bipartite Graphs

Given two sets of vertices $U$ (size $n$) and $V$ (size $m$), how many possibilities of set of edges $E$ exist that make the bipartite graph $G = (U, V, E)$ connected? Obviously there are $2^{n m}$ ...
2
votes
1answer
126 views

Minimum number of vertices to remove to bound the largest connected component of a graph

I have this problem, maybe anybody could help. Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G ...
7
votes
5answers
185 views

Team construction in tri-partite graph

The government wants to create a team with one alchemist, one builder, and one computer-scientist. In order to have good cooperation, it is important that the 3 team-members like each other. ...
11
votes
2answers
195 views

How to practically construct regular expander graphs?

I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices. What is the easiest method to do this in practice? Constructing a random d-regular graph, which is ...
2
votes
1answer
309 views

Maximum number of augmenting paths in a network flow

Let's say we a have flow network with $m$ edges and integer capacities. Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow. A good way to start thinking ...
2
votes
1answer
361 views

Height of a full binary tree

A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children. I have been trying to prove that its height is O(logn) unsuccessfully. Here is my work so far: I ...
5
votes
1answer
240 views

What is the maximum number of shortest paths between any pair of vertices in a chordal graph?

A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a ...
10
votes
1answer
139 views

Number of Hamiltonian cycles on a Sierpiński graph

I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other ...
5
votes
1answer
90 views

Application of Expander Codes

I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon ...
11
votes
1answer
554 views

How many max heaps are there?

How many different max-heaps can I form using a list of $n$ integers. Example: list [1,2,3,4] and max-heap is 4 3 2 1 or ...
3
votes
1answer
187 views

What is the probability of friendship conditioned on the number of mutual friends

Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends? I am ...
8
votes
2answers
820 views

What is the average height of a binary tree?

Is there any formal definition about the average height of a binary tree? I have a tutorial question about finding the average height of a binary tree using the following two methods: The natural ...
5
votes
2answers
2k views

Prove that every two longest paths have at least one vertex in common

If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common. I think that that common vertex ...
7
votes
2answers
356 views

Is there a formal name for this graph operation?

I'm writing a small function to alter a graph in a certain way and was wondering if there is a formal name for the operation. The operation takes two distinct edges, injects a new node between the ...
3
votes
2answers
533 views

How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?

Given a complete binary tree with $n$ nodes. I'm trying to prove that a complete binary tree has exactly $\lceil n/2 \rceil$ leaves. I think I can do this by induction. For $h(t)=0$, the tree is ...
9
votes
1answer
294 views

Number of clique in random graphs

There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of ...
10
votes
2answers
1k views

Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction? For people who were following in the ...