# Tagged Questions

2answers
25 views

### One output for input of $n$-tuples using AND, OR, NOT

Let $B$ be set of $\{0,1\}$ and $B_n$ be the set of all strings of length $n$. How many functions can be constructed from $B_n$ to $B$ using logical operators like AND, OR, NOT. Help $\rightarrow$ ...
1answer
103 views

### What is the mathamatical term for this programming concept?

In python's itertools, there is a function called permutations. It returns the number of ways to arrange x number of variables into a given space. For example, ...
2answers
83 views

### Names of 3 input logic gates

I've tried to look this up online, I may have used the wrong terminology. This question is about the names of logic gates with three boolean inputs, and one boolean output. This is a truth table for ...
0answers
40 views

### Finding whether a sum of numbers in a set generate another number

I have a set of numbers {a1....an} and another number k. I need to find whether sum of any combination of numbers in the set ...
3answers
88 views

### Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days? I think the solution is: $\displaystyle\binom{27}{5}$ But ...
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 ...
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 ...
0answers
13 views

### Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
1answer
47 views

3answers
61 views

### looking for a combinatorial interpretation

given positive integers $n,m$ does the fraction $$\frac{(nm)!}{n!^mm!}$$ count something? Namely does it correspond to the number of possibilities to do something?
2answers
88 views

### What's the term for a value x that satisfies the constraint $f(x) = f$ for a function f?

I know that $x$ is called the fixed point of a function $f$ if it satisfies the constraint $f(x) = x$. However, for a function $f$ if there exists some value $x$ such that $f(x) = f$ then what is the ...
2answers
1k views

### MATLAB code to find distance and eccentricity in graphs

I was trying to find the distances between vertices in graphs. But as the number of vertices are increasing up to 25 vertices or more, its becoming a tedious job for me to calculate $distance$ and ...
1answer
105 views

### An interesting version of the problem “balls into bins”

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
1answer
93 views

### to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
0answers
36 views

### is the $d$-dimensional arrangement of Trees still $NP$-hard?

The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
2answers
215 views

### maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
2answers
79 views

### Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...
1answer
231 views

### diameter and radius of a regular graph

I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
1answer
61 views

### Unique sequences from different sets

I am given $n$ sets with a selection of $m$ elements, such as: $$S = \{\{0\}, \{1, 2, 3\}, \{1, 2, 3\}, \{3\}\}$$ I am trying to calculate the number of unique sequences that contain all elements ...
2answers
88 views

### eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
1answer
82 views

### Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...