Randomly Pk-decomposable graphs

A graph $G$ is $H$-decomposable if it can be expressed as an edge-disjoint union of subgraphs, each subgraph isomorphic to $H$. If $G$ has the additional property that every $H$-decomposable subgraph of $G$ is part of an $H$-decomposition of $G$, then $G$ is randomly $H$-decomposable. Using computer assistance, we provide in this paper a characterization of randomly path-decomposable graphs for paths of length 11 or less. We also prove the following two results: (1) With one small exception, randomly $P_k$-decomposable graphs with a vertex of odd degree do not contain a $P_{k+1}$-subgraph, (2) When the edges of a $P_k$-subgraph are deleted from a connected randomly $P_k$-decomposable graph, the resulting graph has at most one nontrivial component.     

b-coloring of Kneser graphs

A $b$-coloring of a graph $G$ with $k$ colors is a proper coloring of $G$ using $k$ colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer $k$ for which $G$ has a $b$-coloring using $k$ colors is the $b$-chromatic number $b\left(G\right)$ of $G$. The $b$-spectrum $S_b\left(G\right)$ of a graph $G$ is the set of positive integers $k,\chi \left(G\right)\le k\le b\left(G\right)$, for which $G$ has a $b$-coloring using $k$ colors. A graph $G$ is $b$-continuous if $S_b\left(G\right)$ = the closed interval $[\chi \left(G\right),b\left(G\right)]$. In this paper, we obtain an upper bound for the $b$-chromatic number of some families of Kneser graphs. In addition we establish that $[\chi \left(G\right),n+k+1]?S_b\left(G\right)$ for the Kneser graph $G=K(2n+k,n)$ whenever $3\le n\le k+1$. We also establish the $b$-continuity of some families of regular graphs which include the family of odd graphs.     

On k-domination and j-independence in graphs

Let $G$ be a graph and let $k$ and $j$ be positive integers. A subset $D$ of the vertex set of $G$ is a $k$-dominating set if every vertex not in $D$ has at least $k$ neighbors in $D$. The $k$-domination number ${\gamma }_k\left(G\right)$ is the cardinality of a smallest $k$-dominating set of $G$. A subset $I?V\left(G\right)$ is a $j$-independent set of $G$ if every vertex in $I$ has at most $j?1$ neighbors in $I$. The $j$-independence number ${\alpha }_j\left(G\right)$ is the cardinality of a largest $j$-independent set of $G$. In this work, we study the interaction between ${\gamma }_k\left(G\right)$ and ${\alpha }_j\left(G\right)$ in a graph $G$. Hereby, we generalize some known inequalities concerning these parameters and put into relation different known and new bounds on $k$-domination and $j$-independence. Finally, we will discuss several consequences that follow from the given relations, while always highlighting the symmetry that exists between these two graph invariants.     

Moplex orderings generated by the LexDFS algorithm

Let $G$ be a graph with vertex set $V$. A moplex of $G$ is both a clique and a module whose neighborhood is a minimal separator in $G$ or empty. A moplex ordering of $G$ is an ordered partition $(X_1,X_2,?,X_k)$ of $V$ for some integer $k$ into moplexes which are defined in the successive transitory elimination graphs, i.e., for $1?i?k?1$, $X_i$ is a moplex of the graph $G_i$ induced by ${\cup }_{j=i}^k{X}_j$ and $X_k$ induces a clique. In this paper we prove the terminal vertex by an execution of the lexicographical depth-first search (LexDFS for short) algorithm on $G$ belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on $G$ defines a moplex ordering of $G$, which is similar to the result about the maximum cardinality search (MCS for short) algorithm on chordal graphs [J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, IMA Volumes in Mathematics and its Applications, 56 (1993) pp. 1–30] and the result about the lexicographical breadth-first search (LexBFS for short) algorithm on general graphs [A. Berry, J.-P. Bordat, Separability generalizes Dirac’s theorem, Discrete Appl. Math., 84 (1998) 43–53]. As a corollary, we can obtain a simple algorithm on a chordal graph to generate all minimal separators and all maximal cliques.     

Balanced and strongly balanced Pk-designs

Given a graph $G$, a G-decomposition of the complete graph $K_v$ is a set of graphs, all isomorphic to $G$, whose edge sets partition the edge set of $K_v$. A $G$-decomposition of $K_v$ is also called a G-design and the graphs of the partition are said to be the blocks. A $G$-design is said to be balanced if the number of blocks containing any given vertex of $K_v$ is a constant.In this paper the concept of strongly balanced G-design is introduced and strongly balanced path-designs are studied. Furthermore, we determine the spectrum of those path-designs which are balanced, but not strongly balanced.     

Embeddings of rank-2 tori in algebraic groups

Let k be a field of characteristic different from 2 and 3. In this paper we study connected simple algebraic groups of type $A_2$, $G_2$ and $F_4$ defined over k, via their rank-2 k-tori. Simple, simply connected groups of type $A_2$ play a pivotal role in the study of exceptional groups and this aspect is brought out by the results in this paper. We refer to tori, which are maximal tori of $A_n$ type groups, as unitary tori. We discuss conditions necessary for a rank-2 unitary k-torus to embed in simple k-groups of type $A_2$, $G_2$ and $F_4$ in terms of the mod-2 Galois cohomological invariants attached with these groups. The results in this paper and our earlier paper ([6]) show that the mod-2 invariants of groups of type $G_2,F_4$ and $A_2$ are controlled by their k-subgroups of type $A_1$ and $A_2$ as well as the unitary k-tori embedded in them.     

Graph coloring and Graham’s greatest common divisor problem

In this paper we introduce and study two graph coloring problems and relate them to some deep number-theoretic problems. For a fixed positive integer $k$ consider a graph $B_k$ whose vertex set is the set of all positive integers with two vertices $a,b$ joined by an edge whenever the two numbers $a∕gcd(a,b)$ and $b∕gcd(a,b)$ are both at most $k$. We conjecture that the chromatic number of every such graph $B_k$ is equal to $k$. This would generalize the greatest common divisor problem of Graham from 1970; in graph-theoretic terminology it states that the clique number of $B_k$ is equal to $k$. Our conjecture is connected to integer lattice tilings and partial Latin squares completions.     

Fixed-parameter algorithms for vertex cover P3

Let $P_{\ell }$ denote a path in a graph $G=(V,E)$ with $\ell$ vertices. A vertex cover $P_{\ell }$ set $C$ in $G$ is a vertex subset such that every $P_{\ell }$ in $G$ has at least a vertex in $C$. The Vertex Cover$P_{\ell }$ problem is to find a vertex cover $P_{\ell }$ set of minimum cardinality in a given graph. This problem is NP-hard for any integer $\ell ⩾2$. The parameterized version of Vertex Cover$P_{\ell }$ problem called $k$-Vertex Cover$P_{\ell }$ asks whether there exists a vertex cover $P_{\ell }$ set of size at most $k$ in the input graph. In this paper, we give two fixed parameter algorithms to solve the $k$-Vertex Cover$P_3$ problem. The first algorithm runs in time $O^1\left(1.7964^k\right)$ in polynomial space and the second algorithm runs in time $O^1\left(1.7485^k\right)$ in exponential space. Both algorithms are faster than previous known fixed-parameter algorithms.     

Proper connection and size of graphs

An edge-coloured graph $G$ is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph $G,$ denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Our main result is the following: Let $G$ be a connected graph of order $n$ and $k\ge 2$. If $\left|E\left(G\right)\right|\ge \left(\genfrac{}{}{0ex}{}{n?k?1}{2}\right)+k+2$, then $\mathrm{pc}\left(G\right)\le k$ except when $k=2$ and $G\in \{G_1,G_2\},$ where $G_1=K_1\vee (2K_1+K_2)$ and $G_2=K_1\vee (K_1+2K_2).$