Some remarks on Arc-connectivity,vertex splitting,and orientation in graphs and digraphs

We apply proof techniques developed by L. Lovász and A. Frank to obtain several results on the arc-connectivity of graphs and digraphs. The first results concern the operation of splitting two arcs from a vertex of an Eulerian graph or digraph in such a way as to preserve local connectivity conditions. The final result is concerned with orienting the edges of a mixed graph (consisting of vertices, undirected edges, and directed arcs) in such a way that the resulting digraph is as arc-connected as possible.     

Partitioning the edges of a graph

For any integer m (≥2), it is known that there are simple graphs of maximum valence m whose edges cannot be coloured with m colours in such a way that adjacent edges shall have different colours. We find those values of m and k for which it is true that every simple graph whose maximum valence does not exceed mk can be coloured with m colours in such a way that no colour appears more than k times at any vertex.     

The incidence matrix and labelings of a graph

We deal with the problem of labeling the edges of a graph in such a way that the labels of the edges incident with any vertex add up to a value prescribed for that vertex. We show that the use of elementary column operations on the incidence matrix is fruitful in giving easy proofs of theorems on magic graphs and labeling |1, 3, 4|. The method can be visualized in the graph and also leads to a simple proof of a theorem in |2| on the multiplicity of −2 as an eigenvalue of a line graph. We also deal with mixed graphs, the label of a directed edge being subtracted at its initial vertex.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.     

Diameter vulnerability of GC graphs

Concern over fault tolerance in the design of interconnection networks has stimulated interest in finding large graphs with maximum degree Δ and diameter D such that the subgraphs obtained by deleting any set of s vertices have diameter at most D′, this value being close to D or even equal to it. This is the so-called (Δ,D,D′,s)-problem. The purpose of this work has been to study this problem for s=1 on some families of generalized compound graphs. These graphs were designed by Gómez (Ars Combin. 29-B (1990) 33) as a contribution to the (Δ,D)-problem, that is, to the construction of graphs having maximum degree Δ, diameter D and an order large enough. When approaching the mentioned problem in these graphs, we realized that each of them could be redefined as a compound graph, the main graph being the underlying graph of a certain iterated line digraph. In fact, this new characterization has been the key point to prove in a suitable way that the graphs belonging to these families are solutions to the (Δ,D,D+1,1)-problem.     

Representing Groups by Colourings of Graphs

The topic of this paper is representing groups by edge-coloured graphs. Every edge-coloured graph determines a group of graph automorphisms which preserve the colours of the edges. An edge colouring of a graph G is called a perfect one iff every colour class is a perfect matching in G. We prove that every group H and all of its subgroups can be represented (up to isomorphism) by a group of colour preserving automorphisms related to some perfect colouring of the same graph.     

Sufficient Conditions for Super-Arc-Strongly Connected Oriented Graphs

A digraph D is called super-arc-strongly connected if the arcs of every its minimum arc-disconnected set are incident to or from some vertex in D. A digraph without any directed cycle of length 2 is called an oriented graph. Sufficient conditions for digraphs to be super-arc-strongly connected have been given by several authors. However, closely related conditions for super-arc-strongly connected oriented graphs have little attention until now. In this paper we present some minimum degree and degree sequence conditions for oriented graphs to be super-arc-strongly connected.     

A characterization of partial directed line graphs

Can a directed graph be completed to a directed line graph? If possible, how many arcs must be added? In this paper we address the above questions characterizing partial directed line (PDL) graphs, i.e., partial subgraph of directed line graphs. We show that for such class of graphs a forbidden configuration criterion and a Krausz's like theorem are equivalent characterizations. Furthermore, the latter leads to a recognition algorithm that requires O(m) worst case time, where m is the number of arcs in the graph. Given a partial line digraph, our characterization allows us to find a minimum completion to a directed line graph within the same time bound.The class of PDL graphs properly contains the class of directed line graphs, characterized in [J. Blazewicz, A. Hertz, D. Kobler, D. de Werra, On some properties of DNA graphs, Discrete Appl. Math. 98(1-2) (1999) 1-19], hence our results generalize those already known for directed line graphs. In the undirected case, we show that finding a minimum line graph edge completion is NP-hard, while the problem of deciding whether or not an undirected graph is a partial graph of a simple line graph is trivial.     

Two remarks on circular arc graphs

In our first remark we observe a property of circular arcs which is similar to the Helly property and is helpful in describing all maximal cliques in circular arc graphs (as well as allowing us to genralize a result of Tucker). Our main result is a new simple characterization of circular arc graphs of clique covering number two. These graphs play a crucial role in recognition algorithms for circular arc graphs, and have been characterized by several authors. Specifically, we show that a graph with clique covering number two is a circular arc graph if and only if its edges can be coloured by two colours so that no induced four-cycle contains two opposite edges of the same colour. Our proof of the characterization depends on the lexicographic method we have recently introduced. Both remarks could be useful in designing efficient algorithms for (maximum cliques in, respectively recognition of) circular arc graphs     

Eigenvalues of the Laplacian of a graph

Let G be a finite undirected graph with no loops or multiple edges. We define the Laplacian matrix of G,Δ(G)by Δ_ij= degree of vertex i and Δ_ij-1 if there is an edge between vertex i and vertex j. In this paper we relate the structure of the graph G to the eigenvalues of A(G): in particular we prove that all the eigenvalues of Δ(G) are non-negative, less than or equal to the number of vertices, and less than or equal to twice the maximum vertex degree. Precise conditions for equality are given.     

A Note on Large Rainbow Matchings in Edge-coloured Graphs

A rainbow subgraph in an edge-coloured graph is a subgraph such that its edges have distinct colours. The minimum colour degree of a graph is the smallest number of distinct colours on the edges incident with a vertex over all vertices. Kostochka, Pfender, and Yancey showed that every edge-coloured graph on n vertices with minimum colour degree at least k contains a rainbow matching of size at least k, provided ${n\geq \frac{17}{4}k^2}$ . In this paper, we show that n ≥ 4k ? 4 is sufficient for k ≥ 4.     

Polynomial algorithms that prove an NP-Hard hypothesis implies an NP-hard conclusion

A number of results in hamiltonian graph theory are of the form “ implies ”, where is a property of graphs that is NP-hard and is a cycle structure property of graphs that is also NP-hard. An example of such a theorem is the well-known Chvátal–Erd s Theorem, which states that every graph G with κ is hamiltonian. Here κ is the vertex connectivity of G and is the cardinality of a largest set of independent vertices of G. In another paper Chvátal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than κ independent vertices. In this note we point out that other theorems in hamiltonian graph theory have a similar character. In particular, we present a constructive proof of a well-known theorem of Jung (Ann. Discrete Math. 3 (1978) 129) for graphs on 16 or more vertices.     

Graphs whose acyclic graphoidal covering number is one less than its maximum degree

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. In this paper we characterize the class of graphs G for which η_a=Δ−1 where Δ is the maximum degree of a vertex in G.     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

More proofs of menger's theorem

Four ways of proving Menger's Theorem by induction are described. Two of them involve showing that the theorem holds for a finite undirected graph G if it holds for the graphs obtained from G by deleting and contracting the same edge. The other two prove the directed version of Menger's Theorem to be true for a finite digraph D if it is true for a digraph obtained by deleting an edge from D.     

混合图的Hermitian邻接矩阵的零维数

A mixed graph means a graph containing both oriented edges and undirected edges. The nullity of the Hermitian-adjacency matrix of a mixed graph G, denoted by ηH(G),is referred to as the multiplicity of the eigenvalue zero. In this paper, for a mixed unicyclic graph G with given order and matching number, we give a formula on ηH(G), which combines the cases of undirected and oriented unicyclic graphs and also corrects an error in Theorem 4.2 of [Xueliang LI, Guihai YU. The skew-rank of oriented graphs. Sci. Sin. Math., 2015, 45:93-104(in Chinese)]. In addition, we characterize all the n-vertex mixed graphs with nullity n-3, which are determined by the spectrum of their Hermitian-adjacency matrices.     

单圈共轭图的最小广义Randic指标R-1

图G的广义Randic指标定义为Rα=Rα（G）=∑uv∈E（G）（d（u）d（v））^α,其中d（u）是G的顶点u的度,α是任意实数．本文确定了单圈共轭图的广义Randic指标R-1的严格下界,并刻划了达到最小R-1的极图,这类极图还是化学图．     

On the Monotonicity of Process Number

Graph searching games involve a team of searchers that aims at capturing a fugitive in a graph. These games have been widely studied for their relationships with tree-and path-decomposition of graphs. In order to define decompositions for directed graphs, similar games have been proposed in directed graphs. In this paper, we consider such a game that has been defined and studied in the context of routing reconfiguration problems in WDM networks. Namely, in the processing game, the fugitive is invisible, arbitrary fast, it moves in the opposite direction of the arcs of a digraph, but only as long as it has access to a strongly connected component free of searchers. We prove that the processing game is monotone which leads to its equivalence with a new digraph decomposition.     

Perfectly orderable graphs and almost all perfect graphs are kernelM-solvable

A graph is perfectly orderable if and only if it admits an acyclic orientation which does not contain an induced subgraph with verticesa, b, c, d and arcsab, bc, dc. Further a graph is called kernelM-solvable if for every direction of the edges (here pairs of symmetric, i.e. reversible, arcs are allowed) such that every directed triangle possesses at least two pairs of symmetric arcs, there exists a kernel, i.e. an independent setK of vertices such that every other vertex sends some arc towardsK. We prove that perfectly orderable graphs are kernelM-solvable. Using a deep result of Prömel and Steger we derive that almost all perfect graphs are kernelM-solvable.     

Planar acyclic oriented graphs

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.