# All Questions

Tagged with graph-theory co.combinatorics

1,412 questions

**1**

vote

**0**answers

26 views

### Minimum transitive dominating subtournament

For any positive integer $k$, does there exist a tournament such that the smallest dominating set that forms a transitive subtournament has size exactly $k$?
A tournament that does not work for $k>...

**4**

votes

**1**answer

42 views

### Calculate number of vertices adjacent to a clique, but not each other

I have a network of N sensors and a test that tells me whether two sensor outputs are definitely not causally related. This allows me to construct a causality graph where each sensor is a vertex and ...

**0**

votes

**0**answers

15 views

### Difference between Adjacent strong edge coloring and vertex distinguishing strong edge coloring

What is the exact difference between the adjacent strong edge coloring and vertex distinguishing proper edge coloring of graphs? This paper refers to the fact that the adjacent strong edge coloring of ...

**4**

votes

**1**answer

118 views

### Integers with a Hamiltonian Square Path

Let $n>1$ be an integer and set $[n]=\{1,\ldots,n\}$. We say that $n$ has a "Hamiltonian Square Path" if there is a bijection $\varphi:[n]\to[n]$ such that for all $k\in [n-1]$ we have that $\...

**6**

votes

**1**answer

137 views

### Strict unfriendly partitions

Given a graph $G$, an unfriendly partition of $G$ is a partition of $V(G)$ into two classes, such that for every class, every vertex has at least as many neighbors in the other class as in its own ...

**5**

votes

**0**answers

112 views

### A question about dominating circuits in cubic graphs

Let $G$ be a 3-connected cubic graph with a dominating circuit $C$, that is, a circuit such that all edges in $G$ have at least one endvertex in $C$. Let $D$ be another circuit and let the symmetric ...

**2**

votes

**1**answer

93 views

### Edge colorability and Hamiltonicity of certain classes of cubic graphs (MO graphs)

Let $G$ be a simple cubic graph (that is, 3-regular). A dominating circuit of $G$ is a circuit $C$ such that each edge of $G$ has an endvertex in $C$. The circuit $C$ is chordless if no edge which is ...

**2**

votes

**1**answer

148 views

### History of algebraic graph theory

I need a source about the history of algebraic graph theory. I mean for solving which problems or responding to what needs it was created?
Indeed, I want to write a note about the history of the ...

**5**

votes

**1**answer

125 views

### Large dominating sets in tournaments

It is known that in any tournament with $n$ vertices, there is a dominating set of size no more than $\lceil \log_2 n\rceil$. (See Fact 2.5 here.)
What are tournaments such that any dominating set ...

**4**

votes

**1**answer

139 views

### Edge coloring a cycle plus triangles graph and a stronger problem

Let $G$ be a simple “cycle plus triangles” graph, that is, a graph with $3k$ vertices, $k>1$, the edges of which can be partitioned into a set that induces a $3k$-circuit, together with sets that ...

**1**

vote

**1**answer

46 views

### Injective edge choice functions in linear hypergraphs

A linear hypergraph is a hypergraph $H=(V,E)$ such that
for $e\in E$ we have $|e|\geq 2$, and
if $e\neq e_1\in E$, then $|e\cap e_1| \leq 1$.
An injective edge choice function of a linear ...

**2**

votes

**1**answer

47 views

### Number of distinct perfect matchings/near perfect matchings in an induced subgraph

Consider a Class 1 graph with degree $\Delta\ge3$ and the induced subgraph formed by deleting a set of independent vertices of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$. Then, what is ...

**6**

votes

**1**answer

93 views

### Restricted independent set of the cycle graph $C_{3n}$

Let $V$ be the vertices of the cycle graph $C_{3n}$. Suppose there is a partition of $V$ into sets of $3$, i.e. $V=\cup_{k=1}^{n}{V_k}$ where $|V_k|=3$ for $k$ in $1..n$.
QUESTION: Is it possible ...

**0**

votes

**1**answer

60 views

### All even order graphs with $\Delta\ge\frac{n}{2}$ is Class 1

Are all even order graphs with maximum degree $\ge\frac{|V(G)|}{2}$ Class 1(edge-colorable(chromatic index) with $\delta(G)$ colors)? Here, $|V(G)|$ detnotes the number of vertices in the graph.
I ...

**5**

votes

**3**answers

152 views

### Disjunction number of a graph

Let $S\neq \emptyset$ be a set. We make its powerset ${\cal P}(S)$ into a simple, undirected graph by saying that $A, B\in{\cal P}(S)$ form an edge if and only if $A\cap B=\emptyset$.
The ...