On the orientation of meyniel graphs

A kernel of a directed graph is a set of vertices K that is both absorbant and independent (i.e., every vertex not in K is the origin of an arc whose extremity is in K, and no arc of the graph has both endpoints in K). In 1983, Meyniel conjectured that any perfect graph, directed in such a way that every circuit of length three uses two reversible arcs, must have a kernel. This conjecture was proved for parity graphs. In this paper, we extend that result and prove that Meyniel's conjecture holds for all graphs in which every odd cycle has two chords.     

Antimagic orientation of Halin graphs

An antimagic labeling of a digraph $D$ with $n$ vertices and $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$ such that all $n$ oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mütze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation.     

Identity orientation of complete bipartite graphs

An identity orientation of a graph G=(V,E) is an orientation of some of the edges of E such that the resulting partially oriented graph has no automorphism other than the identity. We show that the complete bipartite graph K_s,t, with st, does not have an identity orientation if t3^s-log₃(s-1). We also show that if (r+1)(r+2)2s then K_s,3^s-r does have an identity orientation. These results improve the previous bounds obtained by Harary and Jacobson (Discuss. Math. - Graph Theory 21 (2001) 158). We use these results to determine exactly the values of t for which an identity orientation of K_s,t exists for 2s17.     

Proper orientation number of triangle-free bridgeless outerplanar graphs

An orientation of $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation proper if neighboring vertices have different in-degrees. The proper orientation number of a graph $G$, denoted by $\overrightarrow{\chi }\left(G\right)$, is the minimum maximum in-degree of a proper orientation of $G$. Araujo et al asked whether there is a constant $c$ such that $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le c$ for every outerplanar graph $G$ and showed that $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le 7$ for every cactus $G$. We prove that $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le 3$ if $G$ is a triangle-free 2-connected outerplanar graph and $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le 4$ if $G$ is a triangle-free bridgeless outerplanar graph.     

Alternating orientation and alternating colouration of perfect graphs

We establish a property of minimal imperfect graphs, and use this property to generate two classes of perfect graphs. The first class contains all comparability graphs, all triangulated graphs, and two other classes of perfect graphs. The second class contains all triangulated graphs and all line-graphs of bipartite graphs.     

On the cycle-isomorphism of graphs

This paper considers conditions ensuring that cycle-isomorphic graphs are isomorphic. Graphs of connectivity ? 2 that have no loops were studied in [2] and [4]. Here we characterize all graphs G of connectivity 1 such that every graph that is cycle-isomorphic to G is also isomorphic to G.     

On the net-embeddability of graphs

This paper provides two kinds of forbidden configurations for the rectilinear O-embeddability of triangle free planar graphs. Meanwhile, the characterizations of the O-embeddability for outerplanar graphs and Halin graphs are found.     

On the coverings of graphs

Let ρ(n) denote the smallest integer with the property that any graph with n vertices can be covered by ρ(n) complete bipartite subgraphs. We prove a conjecture of J.-C. Bermond by showing $\text{ρ(n)=n+o(n}{}^{\mathrm{<mtext>11</mtext><mtext>14+?</mtext>}}\text{)}$ for any positive ?.     

On the radius of graphs

Let G be any 3-connected graph containing n vertices and r the radius of G. Then the inequality $\text{r <}\text{1}\text{4}\text{n + O(}\text{log}\text{n)}$ is proved. A similar theorem concerning any (2m ?1)-connected graph G can be proved too.     

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 the embedding of graphs into graphs with few eigenvalues

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic graphs of type k for every k ≥ 3. Furthermore, in the case k ≥ 5 such a family of extensions can be found at every sufficiently large order. Some bounds for the extension will also be given. © 1996 John Wiley & Sons, Inc.     

Lexicographic orientation and representation algorithms for comparability graphs,proper circular arc graphs,and proper interval graphs

We introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent proper circular arc graphs, and to recognize and represent proper interval graphs. As a consequence, we derive and represent proper interval graphs. As a consequence, we derive simple new proofs of a theorem of Ghouila-Houri and a theorem of Skrien. Our algorithms are conceptually simpler than (and often of comparable efficiency to) the existing algorithms for these problems. © 1995 John Wiley & Sons, Inc.     

On the Zagreb indices of the line graphs of the subdivision graphs

The aim of this paper is to investigate the Zagreb indices of the line graphs of the tadpole graphs, wheel graphs and ladder graphs using the subdivision concepts.