# Tagged Questions

**6**

votes

**2**answers

266 views

### Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).
For odd integers $n$ we have $n=\chi(K_n) = ...

**0**

votes

**1**answer

60 views

### average number of cycles and closed walks length k in incomplete directed graph

I asked this question before, but formulation was poor. I've deleted previous question and reformulate it again.
Let graph $G=(N,p)$ is finite simple incomplete directed graph of size $N$ (multiple ...

**5**

votes

**0**answers

88 views

### Mapping graphs to ordinals

Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...

**2**

votes

**0**answers

65 views

### When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...

**2**

votes

**0**answers

49 views

### Looking for similar centrality measurement on graph

I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from ...

**2**

votes

**0**answers

73 views

### Properties of a smallest tournament with domination number $k$

For some tournament $T$, let $\gamma(T)$ denote the cardinality of a smallest dominating set of $T$.
Denote by $f(k)$ the minimum number of vertices of a tournament $T$ having $\gamma(T) = k$.
From ...

**1**

vote

**1**answer

70 views

### Two definitions of genus for circle graphs

In the (very nice) article of Goldstein and Turner untitled Applications of Topological Graph Theory to Group Theory, the following definitions can be found:
Definitions: A circle graph is a pair ...

**6**

votes

**2**answers

223 views

### Cubic graphs whose 2-factors all have the same cycle type

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...

**6**

votes

**1**answer

184 views

### Smallest Connected Graph for Given Degree Sequence

For a given integer sequence $(d_1, d_2,...,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of ...

**2**

votes

**0**answers

164 views

### NP-hard proof of optimization version of exact cover [closed]

Exact cover is NPC.
http://en.wikipedia.org/wiki/Exact_cover#Equivalent_problems
Given a collection $\mathcal{S}$ of subsets of a set $X$, an exact cover is a >>subcollection $\mathcal{S}^*$ ...

**0**

votes

**1**answer

45 views

### Resource on characterizations or properties of traceable graphs

I am looking for some resources that provide information on traceable graphs(paths containing a hamiltonian path). I have found a lot of information on hamiltonian graphs, but none on traceable ...

**0**

votes

**0**answers

75 views

### asymptotic notation with graph colouring

This is my first ever post so I hope this is an appropriate question.
Basically I am looking at the paper here: http://homepages.math.uic.edu/~mubayi/papers/biclique.pdf
Namely theorem 5.
Now, feel ...

**5**

votes

**1**answer

60 views

### Is a connected graph uniquely determined by its weighted 2-step graph?

This is an extension of a previous question: Is a graph uniquely determined by its weighted 2-step graph?. In that question I asked about arbitrary graphs; in this question I restrict to connected ...

**25**

votes

**2**answers

818 views

### Is this graph polynomial known? Can it be efficiently computed?

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...

**7**

votes

**0**answers

92 views

### Set system with prescribed intersection sizes

Questions: What is the asymptotic maximal size of a $4$-uniform (every set has 4 elements) set system $\mathcal{A}$ of subsets of $[n]$ such that, no two sets have size of their intersection $2$?
In ...

**1**

vote

**1**answer

115 views

### edge graph reconstruction conjecture : set vs multi set

Why is the edge reconstruction conjecture stated with the deck defined as the multi set of graphs formed by deleting one edge? Can someone give an example of two graphs such that the edge deleted ...

**7**

votes

**2**answers

311 views

### What is the number of noncrossing acyclic digraphs?

A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...

**5**

votes

**1**answer

135 views

### Graphs where each edge belongs to the same number of 1-factors

Let $G$ be a simple connected graph that has at least one 1-factor. We'll define:
$G$ has property A iff it is edge-transitive.
$G$ has property B iff each edge belongs to the same number of ...

**2**

votes

**0**answers

188 views

### Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate
polynomial which counts the number of colorings of $G$
with $x$ colors for natural $x$.
Graph is not $k$ colorable iff $P(G,k)=0$.
The ...

**1**

vote

**1**answer

142 views

### Vertex transitive and edge transitive and line graph

How can we find the proof of the following statement:
An undirected graph is edge transitive if and only if its line graph is vertex transitive.

**24**

votes

**3**answers

629 views

### Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...

**10**

votes

**2**answers

501 views

### Is every knot unavoidable in the embeddings of some graph?

Is it the case that, for any given knot $K$,
there exists some graph $G$ whose every embedding into $\mathbb{R}^3$
(or into $\mathbb{S}^3$)
contains a cycle that realizes $K$?
I know the ...

**2**

votes

**1**answer

240 views

### How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem).
Restricted GA
Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ ...

**0**

votes

**0**answers

47 views

### Complexity of graph isomorphism in $(P_4 \cup K_1,\overline{3K_2})$-free graphs

Related to this question where isomorphism preserving
transformation maps triangle-free graphs to $(P_4 \cup K_1,\overline{3K_2})$-free graphs.
What is the complexity of graph isomorphism in $(P_4 ...

**3**

votes

**1**answer

115 views

### Graph transformation related to graph isomorphism

Basically got graph transformation related to graph
isomorphism.
Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$.
...

**4**

votes

**1**answer

725 views

### Surprising connection between linear algebra and graph theory

What is the intuition for linear algebra being such an effective tool to resolve questions regarding graphs?
For example, one can determine if a given graph is connected by computing its Laplacian ...

**0**

votes

**0**answers

33 views

### Splitting lemma for digraph and preserving local rooted-edge connectivity?

Let $G$ be a directed graph. $\lambda(x,y,G)$ is the maximum number of edge disjoint paths from $x$ to $y$ in $G$
The local $r$-rooted connectivity of $x$ in $G$ is $\lambda(r,x,G)$.
The global ...

**2**

votes

**1**answer

135 views

### Minimum length path touching $n$ circles

Given $n$ non-overlapping circles of radius $1$ (i.e., the distance between the centers of any two circles is greater than $2$), how to find the minimum length path (the path can be of any form) that ...

**3**

votes

**0**answers

42 views

### Algorithm to construct metric space endomorphism with controlled square

Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be ...

**1**

vote

**1**answer

101 views

### N random walkers that hit node v in a graph

Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...

**2**

votes

**1**answer

84 views

### About the diameter of a graph after removing orientation

This question was posted a few days ago on the Mathematics StackExchange, but so far it has not been answered. Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we ...

**4**

votes

**0**answers

38 views

### What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

The Tutte polynomial
is a bivariate polynomial with positive integer coefficient which is a graph
invariant and can be defined recursively.
Evaluating it is $\#P$-complete even when restricted to ...

**1**

vote

**2**answers

211 views

### Strongly connected DAG from any connected undirected graph?

I have the following question. It seems likely to be true - can anyone provide a standard reference?
Given:
A connected, undirected graph.
Question 1:
Can we assume a single direction for each edge ...

**7**

votes

**0**answers

148 views

### Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...

**3**

votes

**0**answers

92 views

### Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large.
An agent can move in the area at ...

**0**

votes

**0**answers

103 views

### Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$

Valiant
shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$
to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$
for certain efficiently computable $t(F)$ and matrix ...

**6**

votes

**2**answers

185 views

### Find multiple non-adjacent paths in a graph

Consider a non-directed graph. I want to find as many non-adjacent paths as possible from a source $s$ to a destination $t$. Two paths $P_1$ and $P_2$ are said to be non-adjacent to each other if none ...

**4**

votes

**1**answer

116 views

### Product of geodesic distances

I'm working on trying to show this, but can't seem to get started. No guarantees that it is true, but other conditions on the adjacency matrix that make it true or a counter example are helpful. ...

**0**

votes

**2**answers

87 views

### different way of selecting a random graph

Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this ...

**0**

votes

**4**answers

129 views

### about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...

**3**

votes

**1**answer

116 views

### Graphs of lines on del Pezzo surfaces

Let $k$ be an algebraically closed field. To any del Pezzo surface $S$ over $k$ we may associate its graph of lines, which has one vertex for each line and an edge (with multiplicity if required) ...

**2**

votes

**1**answer

182 views

### Clique problem for regular graphs

I am looking for NP complete results for cliques in regular graphs. For example is the general problem of determining if a regular graph on n vertices has an n/2 clique NP-complete? (obviously the ...

**0**

votes

**0**answers

50 views

### Paths on Cartesian products of graphs satisfying linear constraints

Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ ...

**1**

vote

**0**answers

75 views

### Empty node in cactus construction

Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph?
In particular is there a necessary condition for not having empty k-junction ...

**0**

votes

**0**answers

49 views

### Correlation between attributes in a binary graph

Given an unrooted binary tree whose leaves are vertices of degree one that are labelled bijectively by a set $S$. We define a categorical attribute $A$ ($|A|<<|S|$) and each leaf is assigned a ...

**1**

vote

**0**answers

117 views

### Find a path that covers as many nodes as possible

I have the following interesting problem. Given a graph $G$, an agent starts to mark nodes in $G$ in the following way: it marks all nodes within distance $d$ from it. Now the question is to find the ...

**4**

votes

**1**answer

181 views

### Expected number of connected components in a random graph

For a random graph G(n,p) what is the expected number of connected components? What is the probability distribution of this value?
I'm specially interested in what happens for small values of p, ...

**-4**

votes

**1**answer

159 views

### Bipartite graph [closed]

First of all, thank you for your time to reading my post.
I am a researcher but not a mathematician, i have some difficulties in solving a math problem, that why i am here to ask your help. I just ...

**0**

votes

**1**answer

171 views

### Kneser graphs eigenvalues

Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G)) $ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) ...

**7**

votes

**2**answers

211 views

### Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index

Let $\chi'_f(G)$ be the fractional chromatic index.
Based on limited experiments (up to 8 vertices and few larger graphs),
I suspect:
Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = ...