1
vote
3answers
32 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 ...
0
votes
0answers
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 ...
0
votes
1answer
68 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 ...
0
votes
1answer
38 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 ...
2
votes
0answers
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 ...
2
votes
1answer
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? ...
3
votes
2answers
93 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) ...
1
vote
0answers
143 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 ...
1
vote
5answers
131 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 ...
0
votes
1answer
70 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 :)
2
votes
1answer
44 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 ...
4
votes
1answer
226 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 ...
7
votes
1answer
540 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 ...
2
votes
0answers
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 ...
0
votes
2answers
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 ...
3
votes
1answer
304 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 ...
7
votes
2answers
119 views

On doubly graceful permutations

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 ...
3
votes
1answer
193 views

Complexity of counting the number of Good-perfect matching in bipartite 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: ...