Contractible Edges in k-Connected Graphs with Some Forbidden Subgraphs

In 2001, Kawarabayashi proved that for any odd integer k ≥ 3, if a k-connected graph G is \({K^{-}_{4}}\) -free, then G has a k-contractible edge. He pointed out, by a counterexample, that this result does not hold when k is even. In this paper, we have proved the following two results on the subject: (1) For any even integer k ≥ 4, if a k-connected graph G is \({K_{4}^{-}}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge. (2) Let t ≥ 3, k ≥ 2t – 1 be integers. If a k-connected graph G is \({(K_{1}+(K_{2} \cup K_{1, t}))}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge.     

Extremal Problems for Imbalanced Edges

Albertson [2] has introduced the imbalance of an edge e=uv in a graph G as |d_G(u)−d_G(v)|. If for a graph G of order n and size m the minimum imbalance of an edge of G equals d, then our main result states that with equality if and only if G is isomorphic to We also prove best-possible upper bounds on the number of edges uv of a graph G such that |d_G(u)−d_G(v)|≥d for some given d.     

Nonseparating Induced Cycles Consisting of Contractible Edges in k-Connected Graphs

It is proved that if G is a k-connected graph which does not contain K₄⁻, then G has an induced cycle C such that G – V(C) is (k − 2)-connected and either every edge of C is k-contractible or C is a triangle. This theorem is a generalization of some known theorems.     

Removable Edges and Chords of Longest Cycles in 3-Connected Graphs

We verify two special cases of Thomassen’s conjecture of 1976 stating that every longest cycle in a 3-connected graph contains a chord.We prove that Thomassen’s conjecture is true for two classes of 3-connected graphs that have a bounded number of removable edges on or off a longest cycle. Here an edge e of a 3-connected graph G is said to be removable if G – e is still 3-connected or a subdivision of a 3-connected (multi)graph.We give examples to showthat these classes are not covered by previous results.     

The skew chromatic index of a graph

We define a skew edge coloring of a graph to be a set of two edge colorings such that no two edges are assigned the same unordered pair of colors. The skew chromatic index s(G) is the minimum number of colors required for a skew edge coloring of G. We show that this concept is closely related to that of skew Room squares and use this relation to prove that s(G) is at most o(G) + 4. We also find better upper bounds for s(G) when G is cyclic, cubic, or bipartite. In particular we use a construction involving Latin squares to show that if G is complete bipartite of order 2n, s(G) is bounded above by roughly $\text{3n}\text{2}$.     

On finding most uniform spanning trees

We consider the following problem. Given a graph G and a real valued weight for each edge in G, find a spanning tree T of G such that the difference in weight between the most and least weighted edge in T is minimized. We show an O(m log n) algorithm for this problem, where m is the number of edges and n is the number of vertices in G. This algorithm improves the algorithm given by Camerini et al. [1] for the same problem.     

On a Max-min Problem Concerning Weights of Edges

The weight w(e) of an edge e = uv of a graph is defined to be the sum of degrees of the vertices u and v. In 1990 P. Erdős asked the question: What is the minimum weight of an edge of a graph G having n vertices and m edges? This paper brings a precise answer to the above question of Erdős. Received July 12, 1999     

G-decomposition of Kn, where G has four vertices or less

The complete graph K_n, is said to have a G-decomposition if it is the union of edge disjoint subgraphs each isomorphic to G. The set of values of n for which K_n has a G-decomposition is determined if G has four vertices or less.     

Maximum generic nullity of a graph

For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree.     

On the maximal order of cyclicity of antisymmetric directed graphs

A directed graph G without loops or multiple edges is said to be antisymmetric if for each pair of distinct vertices of G (say u and v), G contains at most one of the two possible directed edges with end-vertices u and v. In this paper we study edge-sets M of an antisymmetric graph G with the following extremal property: By deleting all edges of M from G we obtain an acyclic graph, but by deleting from G all edges of M except one arbitrary edge, we always obtain a graph containing a cycle. It is proved (in Theorem 1) that if M has the above mentioned property, then the replacing of each edge of M in G by an edge with the opposite direction has the same effect as deletion: the graph obtained is acyclic. Further we study the order of cyclicity of G (= theminimalnumberofedgesinsuchasetM) and the maximal order of cyclicity in an antisymmetric graph with given number n of vertices. It is shown that for n < 10 this number is equal to the maximal number of edge-disjoint circuits in the complete (undirected) graph with n vertices and for n = 10 (and for an infinite set of n's) the first number is greater than the latter.     

Removable Edges in Longest Cycles of 4-Connected Graphs

Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph G–e; second, for all vertices x of degree 3 in G–e, delete x from G–e and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by Ge. If Ge is 4-connected, then e is called a removable edge of G. In this paper we obtain some results on removable edges in a longest cycle of a 4-connected graph G. We also show that for a 4-connected graph G of minimum degree at least 5 or girth at least 4, any edge of G is removable or contractible.Acknowledgment. The authors are greatly indebted to a referee for his valuable suggestions and comments, which are very helpful to improve the proof of our main result Lemma 3.3.Research supported by National Science Foundation of China AMS subject classification (2000): 05C40, 05C38, 05C75Final version received: March 10, 2004     

Super-connected edge transitive graphs

A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles C_n(n?6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected.     

On the composition factors of a group with the same prime graph as B n (5)

Let G be a finite group. The prime graph of G is a graph whose vertex set is the set of prime divisors of |G| and two distinct primes p and q are joined by an edge, whenever G contains an element of order pq. The prime graph of G is denoted by Γ(G). It is proved that some finite groups are uniquely determined by their prime graph. In this paper, we show that if G is a finite group such that Γ(G) = Γ(B _n (5)), where n ? 6, then G has a unique nonabelian composition factor isomorphic to B _n (5) or C _n (5).     

The edge nucleus of a point-determining graph

In this paper we investigate the edge nucleus E⁰(G) of a point-determining graph G. We observe several relationships between E⁰(G) and the nucleus G⁰ = {v ∈ V(G)∣ G ? v is point determining} and use these relationships to prove several properties of E⁰(G). In particular, we show that there are only a finite number of graphs with a given edge nucleus and we determine those graphs G for which |E⁰(G)| ≤ 2. We also show that an n-clique of a point-determining graph G contains at least n?2 edges of E⁰(G) and if G is totally point determining, then every odd cycle of G meets E⁰(G).     

On Fixed Edges and Edge-Reconstruction of Series-Parallel Networks

 An edge e of a graph G is said to be a fixed edge if G−e+e ^′≅G implies that e ^′=e, and a forced edge if G−e+e ^′ is an edge-reconstruction of G implies that e ^′=e. In this paper, we use the method of excludable configurations to investigate the fixed edges and the forced edges of series-parallel networks. It is proved that all series-parallel networks contain fixed edges except P ₃∨K ₁ and P ₄∨K ₁, and that all series-parallel networks are edge-reconstructible. Received: December 22, 1997 Final version received: July 21, 1999     

On the 1-factors of n-connected graphs

L. W. Beineke and M. D. Plummer have recently proved [1] that every n-connected graph with a 1-factor has at least n different 1-factors. The main purpose of this paper is to prove that every n-connected graph with a 1-factor has at least as many as n(n − 2)(n − 4) … 4 · 2, (or: n(n − 2)(n − 4) … 5 · 3) 1-factors. The main lemma used is: if a 2-connected graph G has a 1-factor, then G contains a vertex V (and even two such vertices), such that each edge of G, incident to V, belongs to some 1-factor of G.     

On total chromatic number of direct product graphs

Coloring of the graph products, especially vertex and edge coloring, has been widely researched for all types of graph products. For total graph coloring, as combination of edge and vertex coloring, Behzad and Vizing set Total Coloring Conjecture in mid 1960s. In this paper, we prove the conjecture for two specific direct graph products, for direct product of path and arbitrary graph G, P _n ×G, where χ′(G)=Δ(G), and expand the proof onto direct product of arbitrary cycle and a path P _n , C _m ×P _n . At the same time, the proofs provide the algorithms to color such graphs.     

On Graphs Without Multicliqual Edges

An edge which belongs to more than one clique of a given graph is called a multicliqual edge. We find a necessary and sufficient condition for a graph H to be the clique graph of some graph G without multicliqual edges. We also give a characterization of graphs without multicliqual edges that have a unique critical generator. Finally, it is shown that there are infinitely many self-clique graphs having more than one critical generator.     

An edge-deletion problem for locally finite graphs

For each positive integer n, let T_n be the tree in which exactly one vertex has degree n and all the other vertices have degree n + 1. A graph G is called stable if its edge set is nonempty and if deleting an arbitrary edge of G there is always a component of the residue graph which is isomorphic to G. The question whether there are locally finite stable graphs that are not isomorphic to one of the graphs T_n is answered affirmatively by constructing an uncountable family of pairwise nonisomorphic, locally finite, stable graphs. Further, the following results are proved: (1) Among the locally finite trees containing no subdivision of T₂, the oneway infinite path T₁ is the only stable graph. (2) Among the locally finite graphs containing no two-way infinite path, T₁ is also the only stable graph.     

Quasirecognition by prime graph of finite simple groups L n (2) and U n (2)

Let G be a finite group. The prime graph ??(G) of G is defined as follows. The vertices of ??(G) are the primes dividing the order of G and two distinct vertices p, p?? are joined by an edge if G has an element of order pp??. Let L=L _n (2) or U _n (2), where n?R17. We prove that L is quasirecognizable by prime graph, i.e. if G is a finite group such that ??(G)=??(L), then G has a unique nonabelian composition factor isomorphic to L. As a consequence of our result we give a new proof for the recognition by element orders of L _n (2). Also we conclude that the simple group U _n (2) is quasirecognizable by element orders.