On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

On cover-structure graphs

Motivated by a problem in communication complexity, we study cover-structure graphs (cs-graphs), defined as intersection graphs of maximal monochromatic rectangles in a matrix. We show that not every graph is a cs-graph. Especially, squares and odd holes are not cs-graphs.It is natural to look at graphs (beautiful graphs) having the property that each induced subgraph is a cs-graph. They form a new class of Berge graphs. We make progress towards their characterization by showing that every square-free bipartite graph is beautiful, and that beautiful line graphs of square-free bipartite graphs are just Path-or-Even-Cycle-of-Cliques graphs.     

On unretractive graphs

The present paper proves necessary and sufficient conditions for both lexicographic products and arbitrary graphs to be unretractive. The paper also proves that the automorphism group of a lexicographic product of graphs is isomorphic to a wreath product of a monoid with a small category.     

On unimodular graphs

We study graphs whose adjacency matrices have determinant equal to 1 or −1, and characterize certain subclasses of these graphs. Graphs whose adjacency matrices are totally unimodular are also characterized. For bipartite graphs having a unique perfect matching, we provide a formula for the inverse of the corresponding adjacency matrix, and address the problem of when that inverse is diagonally similar to a nonnegative matrix. Special attention is paid to the case that such a graph is unicyclic.     

On betweenness-uniform graphs

The betweenness centrality of a vertex of a graph is the fraction of shortest paths between all pairs of vertices passing through that vertex. In this paper, we study properties and constructions of graphs whose vertices have the same value of betweenness centrality (betweenness-uniform graphs); we show that this property holds for distanceregular graphs (which include strongly regular graphs) and various graphs obtained by graph cloning and local join operation. In addition, we show that, for sufficiently large n, there are superpolynomially many betweenness-uniform graphs on n vertices, and explore the structure of betweenness-uniform graphs having a universal or sub-universal vertex.     

On Gorenstein graphs

We classify all Gorenstein claw-free graphs. Moreover, we provide a new way to construct a Gorenstein graph from another one.

     

On supercompact graphs

A graph G is called a supercompact graph if G is the intersection graph of some family ?? of subsets of a set X such that ?? satisfies the Helly property and for any x≠y in X, there exists S ∈ ?? with x ∈ S, y ? S. Various characterizations of supercompact graphs are given. It is shown that every clique-critical graph is supercompact. Furthermore, for any finite graph, H, there is at most a finite number of different supercompact graphs G such that H is the clique-graph of G.     

On brittle graphs

Chvátal defined a graph G to be brittle if each induced subgraph F of G contains a vertex that is not a midpoint of any P₄ or not an endpoint of any P₄. Every brittle graph is perfectly orderable. In this paper, we prove that a graph is brittle whenever it is HHD-free (containing no chordless cycle with at least five vertices, no cycle on six vertices with a long chord, and no complement of the chordless path on five vertices). We also design an O(n₄) algorithm to recognize HHD-free graphs, and also an O(n₄) algorithm to construct a perfect order of an HHD-free graph. It follows from this result that an optimal coloring and a largest clique of an HHD-free graph can be found in O(n₄) time.     

On permutation graphs

We give an upper bound of the number of edges of a permutation graph. We introduce some necessary conditions for a graph to be a permutation graph, and we discuss the independence of these necessary conditions. We show that they are altogether not sufficient for a graph to be a permutation graph.     

On cubical graphs

It is frequently of interest to represent a given graph G as a subgraph of a graph H which has some special structure. A particularly useful class of graphs in which to embed G is the class of n-dimensional cubes. This has found applications, for example, in coding theory, data transmission, and linguistics. In this note, we study the structure of those graphs G, called cubical graphs (not to be confused with cubic graphs, those graphs for which all vertices have degree 3), which can be embedded into an n-dimensional cube. A basic technique used is the investigation of graphs which are critically nonembeddable, i.e., which can not be embedded but all of whose subgraphs can be embedded.     

On Sturmian graphs

In this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.     

On unavoidable graphs

How many edges can be in a graph which is forced to be contained in every graph onn vertices ande edges? In this paper we obtain bounds which are in many cases asymptotically best possible.     

On -connected graphs

A graph is called -connected if is -edge-connected and is -edge-connected for every vertex . The study of -connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a -vertex-connected orientation if and only if it is (2,2)-connected. In this paper, we provide a construction of the family of -connected graphs for even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)-connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph and an integer , what is the minimum number of edges to be added to make -connected. Both these results are based on a new splitting-off theorem for -connected graphs.     

线团-收敛图

一个图的线团图就是这个图的线图的团图。对于自然数n，一个图被称为n-线团－收敛的，如果它的n次线团图同构于一个固定的图。否则称之为发散的。本刻画了线团－收敛图与发散图，给出一个线团－收敛图的构造方法，并且，讨论了线团－收敛图的线团－收敛指数。     

On hamiltonian-connected graphs

One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ? V(G), then G is hamiltonian-connected. We generalize this result using set degrees. That is, for S ? V(G), let deg S = |_x?S N(x)|, where N(x) = {v|xv ? E(G)} is the neighborhood of x. In particular we show: In a 3-connected graph G, if deg S₁ + deg S₂ ≧ |V(G)| + 1 for each pair of distinct 2-sets of vertices S₁, S₂ ? V(G), then G is hamiltonian-connected. Several corollaries and related results are also discussed.     

On replete graphs

A graph G is k-clique replete if G has clique number k and every elementary homomorphism of G has clique number greater than k. Results on the order of k-clique replete graphs are presented, and bounds for the minimum degree and the maximum degree of such graphs are discussed.     

On point-halfspace graphs

The following definition is motivated by the study of circle orders and their connections to graphs. A graphs G is called a point-halfspace graph (in R ^k) provided one can assign to each vertex v ? (G) a point p _v R ^k and to each edge e ? E(G) a closed halfspace H_e ? R ^k so that v is incident with e if and only if p _v ? H_e. Let H ^k denote the set of point-halfspace graphs (in R ^k). We give complete forbidden subgraph and structural characterizations of the classes H ^k for every k. Surprisingly, these classes are closed under taking minors and we give forbidden minor characterizations as well. © 1996 John Wiley & Sons, Inc.     

On factor-invariant graphs

We classify trivalent vertex-transitive graphs whose edge sets have a partition into a Hamilton cycle and a 1-factor that is invariant under the action of the full automorphism group.