Diamtere of ismomorphic graphs – Computer Science Stack Exchange

Thanks for contributing an answer to Computer Science Stack Exchange!

  • Please be sure to answer the question. Provide details and share your research!

But avoid

  • Asking for help, clarification, or responding to other answers.
  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

graphs – Understand Label Cover problem

How is the Label Cover problem related to similar problems such as Vertex Cover, Set Cover and graph coloring? When I read about the Label Cover problem then it seems that it is a generalization and that graph coloring problem can be written as a special case of Label Cover problem. Did I understand at least part of it? I found the original article about it “The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations” and after reading it twice I almost understand the meaning of the Label Cover problem.

Three Clique sums of Bounded Treewidth and Bounded Genus graphs

It is known from the graph minor theory of Robertson and Seymour that H minor free graphs can be expressed as three clique sums of bounded treewidth graphs and planar graphs if H can be drawn in plane with at most one crossing (i.e. for a particular one crossing graph H, there exists). If I understand correctly, this means that given a constant t, if we look at the class of graphs (say F) formed by taking three clique sums of pieces that are either planar of have treewidth <= k, then the forbidden minors of this class all have crossing number at most one.

Is there a similar nice characterization for the class of graphs that can can be expressed as three clique sums of graphs with bounded treewidth or bounded genus(instead of planar)? What all can we say about H if we characterize the family with its forbidden minors ? (The family is minor closed right?)

graphs – Designing an algorithm that finds two nodes of a distance and proving claims

I have to give an algorithm that finds two nodes whose distance is at least half of the diameter of a graph (Given an undirected connected graph G), knowing that the diameter of a graph is the largest distance between any two nodes. The nodes are unweighted.
The general idea is to run BFS from any arbitrary node, and find two nodes that fulfill the requirement but the difficulty for me lies in formally proving any claim used.

Is a possible solution to have an algorithm that runs BFS from a node to calculate the diameter, and then in the stored list to find two nodes that are at least half that diameter? Or is there a more optimal solution?
I am a first year CS student, so any guidance or help would be appreciated!

A communication problem about graphs

An undirected graph on $n$ vertices and $n-1$ edges $G = (V,E)$ is partitioned between two players $A$ and $B$ such that $A$ knows $(V,E_A)$, $B$ knows $(V,E_B)$ and $E_A dotcup E_A = E$.

Initially, $B$ receives an advice $m_1$ that depends on $G$ and the given partition. After that, $B$ receives a randomized message $m_2$ from $A$, and has to decide whether $G$ is connected or not. If $G$ is connected, then there should be an advice $m_1$ such $B$ will accept with probability at least $2/3$. If it does not, then for any given advice $m_1$, $B$ will accept with probability at most $1/3$.

Is it possible to achieve such a protocol with $m_1 = o(n)$ and $m_2 = o(n)$?

co.combinatorics – List total chromatic number of complete graphs

Since for an odd integer $n$, a complete graph on $n$ vertices is list-edge-$n$ choosable, and the total chromatic number is $n$, it is easy to see that the list total chromatic number is bounded above by $n+2$ by a greedy algorithm.

My question is, can the bound be reduced further to obtain, say the that the list total chromatic number is $n+1$, or the optimal $n$? I was thinking along the lines of the list total chromatic number can be bounded above by $text{max(list chromatic index, total chromatic number)}+1$ for any graph. Any counterexamples to this fact? Thanks beforehand.

graphs – Clustering algorithm for grouping polygons with the same sides into clusters

Given a number of specific type polygons (i.e., each polygon has the same number of sides but the shape could be different), is there any clustering algorithm that can be used to group all of them into clusters?

For example, given 50 hexagons with different shapes, I want to group all of them into 4 clusters according to their similarity.

graphs – Relationships between centrality metrics?

I am studying graph centrality, and came across a very nice table in here (reproducing it below, all credit goes to the original authors Shaikh Arifuzzaman and Md Hasanuzzaman Bhuiyan).

enter image description here

I have computed some correlations between centrality metrics based on a network that I have, but I’m having trouble interpreting what I’m finding. Specifically:

  • Correlation degree vs eccentricity is negative, but degree vs closeness is positive: this means that many central nodes are very “close” to most nodes in the network, but how to interpret this with respect to eccentricity (i.e. longest paths)?
  • Correlation eccentricity vs closeness is negative: can this mean that some nodes are very close to most of the nodes in the network, but many longest paths pass through those nodes? I’m having a hard time interpreting this.
  • Eigenvector centrality correlates positively with degree and closeness (understandably), but shows no correlation with eccentricity or betweenness.

I would really appreciate any help in understanding this.

algorithms – DAG decomposition similar to series-parallel graphs

Let’s consider directed acyclic graphs (DAGs) with single source and single sink. Such graphs can be combined with two operations, used in Series-Parallel graphs – parallel composition $P$ and series composition $S$.

I’m interested in reverse operation (i.e. decomposition) – given a DAG $G_1$ I want to get a DAG $G_2$, where all the subgraphs, which can’t be decomposed further using operations, reverse to $P$ and $S$, are replaced by nodes. For example, the graph $G1$ below can be decomposed in this way – three subgraphs, which can’t be decomposed further are replaced by nodes (in red color). Note, that all such non-decomposable subgraphs with two vertices (simply arcs – in green color) aren’t replaced by nodes.


I know that the series decomposition can be done in linear time (it’s equivalent to finding articulation points). The parallel decomposition looks harder, also it’s unclear what operation should be tried first at each decomposition step.

Are there any existing algorithms, which can find such decomposition?