Interval Minors of Complete Bipartite Graphs

Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley–Wilf limits. We investigate the maximum number of edges in ‐interval minor‐free bipartite graphs. We determine exact values when and describe the extremal graphs. For , lower and upper bounds are given and the structure of ‐interval minor‐free graphs is studied.     

A Characterization of Mixed Unit Interval Graphs

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half‐open unit intervals of the real line. This is a proper superclass of the well‐known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach, and Szwarcfiter (Mixed unit interval graphs, Discrete Math 312, 3357–3363 (2012)).     

Unit Interval Graphs of Open and Closed Intervals

We give two structural characterizations of the class of finite intersection graphs of the open and closed real intervals of unit length. This class is a proper superclass of the well‐known unit interval graphs.     

Interval Non‐edge‐Colorable Bipartite Graphs and Multigraphs

An edge‐coloring of a graph G with colors is called an interval t‐coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erd?s constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erd?s's counterexample is the smallest (in a sense of maximum degree) known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non‐edge‐colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.     

Edge-Coloring Bipartite Graphs

Given a bipartite graph G with n nodes, m edges, and maximum degree Δ, we find an edge-coloring for G using Δ colors in time T + O(m log Δ), where T is the time needed to find a perfect matching in a k-regular bipartite graph with O(m) edges and k ≤ Δ. Together with best known bounds for T this implies on edge-coloring algorithm which improves on the algorithm of Hopcroft and Cole. Our algorithm can also be used to find a (Δ + 2)-edge-coloring for G in time O(m log Δ). The previous best approximation algorithm with the same time bound needed Δ + log Δ colors.     

Split Permutation Graphs

The class of split permutation graphs is the intersection of two important classes, the split graphs and permutation graphs. It also contains an important subclass, the threshold graphs. The class of threshold graphs enjoys many nice properties. In particular, these graphs have bounded clique-width and they are well-quasi-ordered by the induced subgraph relation. It is known that neither of these two properties is extendable to split graphs or to permutation graphs. In the present paper, we study the question of extendability of these two properties to split permutation graphs. We answer this question negatively with respect to both properties. Moreover, we conjecture that with respect to both of them the split permutation graphs constitute a critical class.     

二部图的E-H-不可收缩性

By End（G） and hEnd（G） we denote the set of endomorphisms and half-strong endomorphisms of a graph G respectively. A graph G is said to be E-H-unretractive if End（G） = hEnd（G）. A general characterization of an E-H-unretractive graph seems to be difficult. In this paper, bipartite graphs with E-H-unretractivity are characterized explicitly.     

Bipartite Graphs and Monochromatic Squares

Order - Let κ be a successor cardinal. We prove that consistently every bipartite graph of size κ+ × κ+ contains either an independent set or a clique of size τ ×...     

Maximal Energy Bipartite Graphs

 Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then

Chaotic Numbers of Complete Bipartite Graphs and Tripartite Graphs

In this paper, we study the chaotic numbers of complete bipartite graphs and complete tripartite graphs. For the complete bipartite graphs, we find closed-form formulas of the chaotic numbers and characterize all chaotic mappings. For the complete tripartite graphs, we develop an algorithm running in O(n ⁴ ₃) time to find the chaotic numbers, with n ₃ the number of vertices in the largest partite set.Research supported by NSC 90-2115-M-036-003.The author thanks the authors of Ref. 6, since his work was motivated by their work. Also, the author thanks the referees for helpful comments which made the paper more readable.     

二部图的单特征值

一个图的特征值通常指的是它的邻接矩阵的特征值,在图的所有特征值中,重数为1的特征值即所谓的单特征值具有特殊的重要性.确定一个图的单特征值是一个比较困难的问题,主要是没有一个通用的方法.1969年,Petersdorf和Sachs给出了点传递图单特征值的取值范围,但是对于具体的点传递图还需要根据图本身的特性来确定它的单特...     

A Characteristic Approach to Bipartite Graphs and Incidence Graphs

A ‘bipartite characteristic’ parameter is defined for bipartite graphs that mimics the (Euler) characteristic—the number of vertices, minus the number of edges, plus the number of triangles, minus the number of 4-cliques, etc.—of general graphs. This allows the characterization of linear, totally balanced, acyclic, tree, and biacyclic hypergraphs in terms of the bipartite characteristic values of their incidence graphs.     

Enumeration of Bipartite Self-Complementary Graphs

Let e(m, n), o(m, n), bsc(m, n) be the number of unlabelled bipartite graphs with an even number of edges whose partite sets have m vertices and n vertices, the number of those with an odd number of edges, and the number of unlabelled bipartite self-complementary graphs whose partite sets have m vertices and n vertices, respectively. Then this paper shows that the equality bsc(m, n) = e(m, n) ? o(m, n) holds.     

Amalgams of Cubic Bipartite Graphs

The amalgamation technique has been introduced for groups by Higman et al. [8] and Goldschmidt [7] and developed on geometries by Kegel and Schleiermacher [9]. We define a “graph amalgam” to point out a different approach to certain classes of cubic bipartite graphs. Furthermore, we find relations between graph amalgams, 3-bridges and star-products of cubic bipartite graphs.     

Tails of Bipartite Distance-regular Graphs

Let Γ denote a bipartite distance-regular graph with diameterD  ≥  4 and valency k ≥  3. Let θ 0  > θ 1  >  >  θD denote the eigenvalues of Γ and let E₀, E₁, , E_Ddenote the associated primitive idempotents. Fix s(1  ≤  s ≤  D −  1 ) and abbreviate E: =  E_s. We say E is a tail whenever the entrywise product E   E is a linear combination of E₀, E and at most one other primitive idempotent of Γ. Letq_ij^{σi + 1 h} (0  ≤ h , i, j ≤  D) denote the Krein parameters of Γ and letΔ denote the undirected graph with vertices 0, 1, , D where two vertices i, j are adjacent whenever i ≠  =  j andq_ij^σi + 1s  ≠  =  0. We show E is a tail if and only if one of (i)–(iii) holds: (i) Δ is a path; (ii) Δ has two connected components, each of which is a path; (iii) D =  6 and Δ has two connected components, one of which is a path on four vertices and the other of which is a clique on three vertices.     

A Characterization of the Optimal p-sum Labellingsof Unit Interval Graphs

1.IntroductionGraphsconsideredinthispaperarefiniteandsimple.FOragraphG,V(G)andE(G)denoteitssetofvenicesandedges,respectively.AbijectionwillbecalledalabellingofG.Letpbeapositiverealnumber.ForagivenlabellingTofagraphG,definethegndiscrepencya.(G,ac)ofTasTheobjectiveoftheminimum-p--sumproblemistofindalabelling7ofagraphGsuchthatac(G,T)isassmallaspossible.ThelabellingTminimizinga.(G,7)iscalledanoptimalHsumlabellingofG.Theminimumvalueiscalledtheminimum-psumofG.ItisshowninI31thattheminimum-…     

Perfect Elimination and Chordal Bipartite Graphs

We define two types of bipartite graphs, chordal bipartite graphs and perfect elimination bipartite graphs, and prove theorems analogous to those of Dirac and Rose for chordal graphs (rigid circuit graphs, triangulated graphs). Our results are applicable to Gaussian elimination on sparse matrices where a sequence of pivots preserving zeros is sought. Our work removes the constraint imposed by Haskins and Rose that pivots must be along the main diagonal.     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

Ramsey Numbers of Some Bipartite Graphs Versus Complete Graphs

The Ramsey number r(H, K _n ) is the smallest positive integer N such that every graph of order N contains either a copy of H or an independent set of size n. The Turán number ex(m, H) is the maximum number of edges in a graph of order m not containing a copy of H. We prove the following two results: (1) Let H be a graph obtained from a tree F of order t by adding a new vertex w and joining w to each vertex of F by a path of length k such that any two of these paths share only w. Then r(H,K_n) ￡ c_k,t [(n^1+1/k)/(ln^1/k n)]{r(H,K_n)\leq c_{k,t}\, {n^{1+1/k}\over \ln^{1/k} n}} , where c _k,t is a constant depending only on k and t. This generalizes some results in Li and Rousseau (J Graph Theory 23:413–420, 1996), Li and Zang (J Combin Optim 7:353–359, 2003), and Sudakov (Electron J Combin 9, N1, 4 pp, 2002). (2) Let H be a bipartite graph with ex(m, H) = O(m ^γ ), where 1 < γ < 2. Then r(H,K_n) ￡ c_H ([(n)/(lnn)])^1/(2-g){r(H,K_n)\leq c_H ({n\over \ln n})^{1/(2-\gamma)}}, where c _H is a constant depending only on H. This generalizes a result in Caro et al. (Discrete Math 220:51–56, 2000).