2
$\begingroup$

I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below

Description :

$G$ is a $r$ regular graph, $k$ connected( not a complete , cycle graph). A vertex of $G$ is $x_1$. All vertices which are not adjacent to $x_1$ create a sub-graph $C_1$. All vertices adjacent to $x_1$ create a sub-graph $, D_1 $. A vertex of $D_1$ is $x_2$.

Using same method, based on adjacency of $x_2$ , $D_1$ can be divided.

All vertices which are not adjacent to $x_2$ create a sub-graph $C_2$.

All vertices adjacent to $x_2$ create a sub-graph $, D_2 $. In general , $ D_{y-1} $ is a graph and can be divided/ partitioned in to 2 sub graphs $C_y, D_y $ .

There are 2 restrictions, they are-

  1. $C_y, D_y $ are $s_y , t_y > 0 ; s_y \neq t_y; $ regular graphs respectively for all iteration $y$

  2. $C_y, D_y $ cannot be complete bipartite graph (utility graph), complete graph or disjoint union of complete graphs.

    $G$ can be divided/ partitioned maximum $\log_2(|G|)$ times , using this dividing process recursively if $G$ is a 3 clique free graph , this condition implies $t_y \leq |D_y|/2$.

Questions :

Does there exist such graph in current literature as described above(follows restriction 1 or 2 or both)?

Motivation : An algorithm runs faster than existing results for this kind of graphs.

Related papers:

  1. V.A.Taskinov. Regular subgraphs of regular graphs. Sov.Math.Dokl.26(1982), 37-38 . In this paper he proved the following : Let $0<k<r$ be positive odd integers. Then every $r$-regular graph contains a $k$-regular subgraph (Here, the graph need not be simple).

  2. N. ALON,S. FRIEDLAND,G. KALAI. Regular Subgraphs of Almost Regular Graphs. JOURNAL OF COMBINATORIAL THEORY, Series B 37, 79-91 (1984)

    Any advice will help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.