Vertex pancyclicity in quasi claw-free graphs

This paper generalizes the concept of locally connected graphs. A graph G is triangularly connected if for every pair of edges e₁,e₂∈E(G), G has a sequence of 3-cycles C₁,C₂,…,C_l such that e₁∈C₁,e₂∈C_l and E(C_i)∩E(C_i+1)≠∅ for 1?i?l-1. In this paper, we show that every triangularly connected quasi claw-free graph on at least three vertices is vertex pancyclic. Therefore, the conjecture proposed by Ainouche is solved.     

A note on the recognition of bisplit graphs

We show that bisplit graphs can be recognized in O(n²) time. The previous best bound of O(mn) for the problem appeared in a recently published article [A. Brandstädt, P.L. Hammer, V.B. Le, V.V. Lozin, Bisplit graphs, Discrete Math. 299 (2005) 11-32] in this journal.     

Vertex PI indices of four sums of graphs

Suppose that e is an edge of a graph G. Denote by m_e(G) the number of vertices of G that are not equidistant from both ends of e. Then the vertex PI index of G is defined as the summation of m_e(G) over all edges e of G. In this paper we give the explicit expressions for the vertex PI indices of four sums of two graphs in terms of other indices of two individual graphs, which correct the main results in a paper published in Ars Combin. 98 (2011).     

Vertex pancyclicity in quasi-claw-free graphs

A graph G is called quasi-claw-free if for any two vertices x and y with distance two there exists a vertex u∈N(x)∩N(y) such that N[u]⊆N[x]∪N[y]. This concept is a natural extension of the classical claw-free graphs. In this paper, we present two sufficient conditions for vertex pancyclicity in quasi-claw-free graphs, namely, quasilocally connected and almost locally connected graphs. Our results include some well-known results on claw-free graphs as special cases. We also give an affirmative answer to a problem proposed by Ainouche.     

Efficient algorithms for decomposing graphs under degree constraints

Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321-324] proved that if every vertex v in a graph G has degree d(v)?a(v)+b(v)+1 (where a and b are arbitrarily given nonnegative integer-valued functions) then G has a nontrivial vertex partition (A,B) such that d_A(v)?a(v) for every v∈A and d_B(v)?b(v) for every v∈B. Kaneko [On decomposition of triangle-free graphs under degree constraints, J. Graph Theory 27 (1998) 7-9] and Diwan [Decomposing graphs with girth at least five under degree constraints, J. Graph Theory 33 (2000) 237-239] strengthened this result, proving that it suffices to assume d(v)?a+b (a,b?1) or just d(v)?a+b-1 (a,b?2) if G contains no cycles shorter than 4 or 5, respectively.The original proofs contain nonconstructive steps. In this paper we give polynomial-time algorithms that find such partitions. Constructive generalizations for k-partitions are also presented.     

Vertex reconstruction in Cayley graphs

In this survey paper we review recent results on the vertex reconstruction problem (which is not related to Ulam’s problem) in Cayley graphs. The problem of reconstructing an arbitrary vertex x from its r-neighbors, that are, vertices at distance at most r from x, consists of finding the minimum restrictions on the number of r-neighbors when such a reconstruction is possible. We discuss general results for simple, regular and Cayley graphs. To solve this problem for given Cayley graphs, it is essential to investigate their structural and combinatorial properties. We present such properties for Cayley graphs on the symmetric group and the hyperoctahedral group (the group of signed permutations) and overview the main results for them. The choice of generating sets for these graphs is motivated by applications in coding theory, computer science, molecular biology and physics.     

Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs

We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n² log⁵ n) time and O(n²) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs.     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).     

Bipartite graphs without a skew star

A skew star is a tree with exactly three vertices of degree one being at distance 1, 2, 3 from the only vertex of degree three. In the present paper, we propose a structural characterization for the class of bipartite graphs containing no skew star as an induced subgraph and discuss some applications of the obtained result.     

Uncountable families of vertex-transitive graphs of finite degree

We prove that the set of vertex-transitive graphs of finite degree is uncountably large.     

Vertex magic total labelings of 2-regular graphs

A vertex magic total (VMT) labeling of a graph $G=(V,E)$ is a bijection from the set of vertices and edges to the set of integers defined by $\lambda :V\cup E\to \{1,2,\dots ,|V|+|E\left|\right\}$ so that for every $x\in V$, $w\left(x\right)=\lambda \left(x\right)+{\sum }_{xy\in E}\lambda \left(xy\right)=k$, for some integer $k$. A VMT labeling is said to be a super VMT labeling if the vertices are labeled with the smallest possible integers, $1,2,\dots ,\left|V\right|$. In this paper we introduce a new method to expand some known VMT labelings of 2-regular graphs.     

Split and balanced colorings of complete graphs

An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain K_n in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph K_N has a coloring which is not (r, n)-split is denoted by ƒ_r(n). Balanced (r,n)-colorings are defined as edge r-colorings of KN such that every subset of [N/r] vertices contains a monochromatic K_n in all colors. Then g_r(n) is defined as the smallest N such that K_N has a balanced (r, n)-coloring. The definitions imply that f_r(n) g_r(n). The paper gives estimates and exact values of these functions for various choices of parameters.     

Codes from the incidence matrices of graphs on 3-sets

We examine the p-ary linear codes from incidence matrices of the three uniform subset graphs with vertex set the set of subsets of size 3 of a set of size n, with adjacency defined by two vertices as 3-sets being adjacent if they have zero, one or two elements in common, respectively. All the main parameters of the codes and the nature of the minimum words are obtained, and it is shown that the codes can be used for full error-correction by permutation decoding. We examine also the binary codes of the line graphs of these graphs.     

Codes from lattice and related graphs, and permutation decoding

Codes of length n² and dimension 2n−1 or 2n−2 over the field F_p, for any prime p, that can be obtained from designs associated with the complete bipartite graph K_n,n and its line graph, the lattice graph, are examined. The parameters of the codes for all primes are obtained and PD-sets are found for full permutation decoding for all integers n≥3.     

Recognizing graphs without asteroidal triples

We consider the problem of recognizing AT-free graphs. Although there is a simple O(n³) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in , , and O(n^2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs.     

Two characterisations of the minimal triangulations of permutation graphs

A minimal triangulation of a graph is a chordal supergraph with an inclusion-minimal edge set. Minimal triangulations are obtained from adding edges only to minimal separators, completing minimal separators into cliques. Permutation graphs are the comparability graphs whose complements are also comparability graphs. Permutation graphs can be characterised as the intersection graphs of specially arranged line segments in the plane, which is called a permutation diagram. The minimal triangulations of permutation graphs are known to be interval graphs, and they can be obtained from permutation diagrams by applying a geometric operation, that corresponds to the completion of separators into cliques. We precisely specify this geometric completion process to obtain minimal triangulations, and we completely characterise those interval graphs that are minimal triangulations of permutation graphs.     

On the edge-connectivity and restricted edge-connectivity of a product of graphs

The product graph G_m*G_p of two given graphs G_m and G_p was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32-48]. For this kind of graphs we provide bounds for two connectivity parameters (λ and λ^′, edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs G_m, G_p of minimum degrees δ(G_m), δ(G_p), respectively, we show that λ(G_m*G_p) is lower bounded by both δ(G_m)+λ(G_p) and δ(G_p)+λ(G_m), an improvement of what is known for the edge-connectivity of G_m×G_p.     

Clique-critical graphs: Maximum size and recognition

The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K^-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete.     

A vertex ordering characterization of simple-triangle graphs

Consider two horizontal lines in the plane. A point on the top line and an interval on the bottom line define a triangle between two lines. The intersection graph of such triangles is called a simple-triangle graph. This paper shows a vertex ordering characterization of simple-triangle graphs as follows: a graph is a simple-triangle graph if and only if there is a linear ordering of the vertices that contains both an alternating orientation of the graph and a transitive orientation of the complement of the graph.