# Tagged Questions

17 views

### Total number of possible graphs in a network with $m$ edges and $n$ vertices?

How do you calculate the total number of possible graphs in a network with $m$ undirected edges and $n$ vertices? No self-loops. For instance, if I have a network with $7$ vertices in it, I want to ...
59 views

### Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
34 views

### Signing the attendance

Imagine N students sitting in a straight row, students are numbered 1 to N. Attendance sheet is first given to student 1, who uses his own pen to sign the sheet. Then he passes the sheet to student 2, ...
34 views

### Generalize the number of total overall hops possible in a line network

Suppose I have a network of computers arranged in a line, like in the image I made below. I want to know the total number of hops possible. For example, $A$ gets to $B$ in $1$ hop, to $C$ in $2$ and ...
47 views

### show permutation graph is a perfect graph

I need to prove that permutation graph is a perfect graph. I've shown that for any $i<j$, $\{i,j\}$ connected iff $f(i)>f(j)$. In addition, I know that the complement of a permutation graph is a ...
87 views

### Assignment problem with unique “unemployment” costs

Given $w$ workers and $k < w$ tasks, the usual integer cost matrix $(c_{ij})$ for the cost of assigning worker $i$ to task $j$ and a cost vector $(u_p)$ which assigns any selection $p$ of ...
41 views

### Total number of ways to color a regular graph.

I have problem stating "Find total number of ways to color a regular pentagon with 5 colors." If we consider(Exact 5 colors to color the graph) it unlabeled graph then it will be the same to ...
65 views

### How many different ways can 10 octupuses touch legs?

There are 10 octopuses (octopi?). Each octopus has 8 legs. Legs on an octopus can only touch touch legs on other octupuses. Assuming each leg touches exactly 1 other leg, how many different ...
94 views

### How many matrix colorings are possible?

We have a small square matrix having size up to $8$. And we have a large number of colors up to $10^6$. In how many ways we can color the matrix so that all the same color cells are not adjacent? ...
103 views

### Example of a simple graph isomorphic to a permutation group.

I'm taking a first course in graph theory this semester and I'm working trough Graph Theory with Applications by J.A. Bonday and U.S.R. Murty. I can't find an answer to question 1.2.12(f): (a) ...
151 views

### Count the number of restricted multigraphs

Suppose I have a multigraph with the following set of restrictions: every vertex can have up to $c$ edges two vertices can be connected by a maximum of $c-1$ edges loops may or may not be allowed ...
136 views

### When is round-robin scheduling possible and with in minimal time?

Suppose that you have six teams $x_0, x_1, x_2, x_3, x_4, x_5$. Can you schedule round-robin games between them so that if one game is played each day, the series of games can be completed in five ...
71 views

### Number of ways to arrange $n$ numbered vertices in a simple undirected cycle.

I thought it'd be $(n-1)!$ and I've been told it's $(n-1)!/2$ because of a mirror like effect. Can anyone please explain this to me? I can't seem to get the hang of this. Thank you :)
46 views

### Number of Total orders of a dependency graph

Define a dependency graph to be a graph $G=(V,E)$ such that an edge between vertices $v$ and $u$ in $V$ is present if $v<u$ i.e. $v$ comes before $u$ in our ordering (I'm not very concise here, I ...
255 views

### Wreath Products of Symmetric Groups

I am currently in the process of reading an article by D.Bundy The connectivity of commuting graphs. In section 3 (in the Preliminary Results) Bundy gives the following result: $\mathbf{(3.1)}$ Let ...
544 views

### When does the adjacency or incidence matrix of a graph have consecutive ones property?

Given a graph, what are some sufficient (and necessary) conditions to tell if its adjacency matrix has the consecutive ones property? Similar question for its incidence matrix? Note that a ...
47 views

### Terminology: is there a term for one order being on a geodesic between two others in the Cayley graph?

Think about the graph whose nodes are total orders on a finite set, and whose edges connect orders that only differ on two elements. This is actually a Cayley graph of $S_n$, but I don't want to fix ...
86 views

### Permutating dance partners with least distance moved [duplicate]

Possible Duplicate: Gay Speed Dating Problem There are n (even) people at a dance and they dance in pairs. They do not care about gender (it is a very liberal disco). The goal is for each ...
311 views

### Sliding blocks puzzle

Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square, 1 green, some red and the rest are blue, a move consists of shuffling ...
A permutation $\sigma\in\mathfrak S_n$ is graceful if $$\{|\sigma(i+1)-\sigma(i)| \text{ with } 1\leq i\leq n\}=\{1,2,\ldots,n-1\}$$ (terminology coming from a more general definition in graph ...
Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$. Definition1: ...