Posets with interval upper bound graphs

Competition graphs of transitive acyclic digraphs are strict upper bound graphs. This paper characterizes those posets, which can be considered transitive acyclic digraphs, which have upper bound graphs that are interval graphs. The results proved here may shed some light on the open question of those digraphs which have interval competition graphs.This material is taken from Chapter 3 of my (maiden name Diny) PhD Dissertation.     

Strongly irreducible ideals of a commutative ring

An ideal I of a ring R is said to be strongly irreducible if for ideals J and K of R, the inclusion J∩K⊆I implies that either J⊆I or K⊆I. The relationship among the families of irreducible ideals, strongly irreducible ideals, and prime ideals of a commutative ring R is considered, and a characterization is given of the Noetherian rings which contain a non-prime strongly irreducible ideal.     

Zero-divisor graphs of amalgamated duplication of a ring along an ideal

Let R be a commutative ring with identity and let I be an ideal of R. Let R?I be the subring of R×R consisting of the elements (r,r+i) for r∈R and i∈I. We study the diameter and girth of the zero-divisor graph of the ring R?I.     

The partial complement of graphs

For a graphG, the switched graphS _v (G) ofG at a vertexv is the graph obtained fromG by deleting the edges ofG incident withv and adding the edges of incident withv. Properties of graphs whereS _v (G) G or are studied. This concept is extended to the partial complementS _H (G) where H . The investigation here centers around the existence of setsH for whichS _H (G) G. A parameter is introduced which measures how near a graph is to being self-complementary.     

Covering of graphs by complete bipartite subgraphs; Complexity of 0–1 matrices

We prove that the edge set of an arbitrary simple graphG onn vertices can be covered by at mostn−[log₂ n]+1 complete bipartite subgraphs ofG. If the weight of a subgraph is the number of its vertices, then there always exists a cover with total weightc(n ²/logn) and this bound is sharp apart from a constant factor. Our result answers a problem of T. G. Tarján. Dedicated to Paul Erdős on his seventieth birthday     

A characterization of graphs with rank 4

The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: What is the structure of a connected graph with rank 4? This question has not yet been fully answered in the literature, and only some partial results are known. In this paper we resolve this question by completely characterizing graphs G whose adjacency matrix has rank 4.     

Almost perfect commutative rings

Almost perfect commutative rings R are introduced (as an analogue of Bazzoni and Salce's almost perfect domains) for rings with divisors of zero: they are defined as orders in commutative perfect rings such that the factor rings $R/Rr$ are perfect rings (in the sense of Bass) for all non-zero-divisors$r\in R$. It is shown that an almost perfect ring is an extension of a T-nilpotent ideal by a subdirect product of a finite number of almost perfect domains. Noetherian almost perfect rings are exactly the one-dimensional Cohen–Macaulay rings. Several characterizations of almost perfect domains carry over practically without change to almost perfect rings. Examples of almost perfect rings with zero-divisors are abundant.     

Vertex decomposability and regularity of very well-covered graphs

A graph is called very well-covered if it is unmixed without isolated vertices such that the cardinality of each minimal vertex cover is half the number of vertices. We first prove that a very well-covered graph is Cohen-Macaulay if and only if it is vertex decomposable. Next, we show that the Castelnuovo-Mumford regularity of the quotient ring of the edge ideal of a very well-covered graph is equal to the maximum number of pairwise 3-disjoint edges.     

Counting substructures I: Color critical graphs

Let F be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of F in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits (1968) [8], who proved that there is one copy of F, and of Rademacher, Erd?s (1962) [1] and [2] and Lovász and Simonovits (1983) [4], who proved similar counting results when F is a complete graph.One of the simplest cases of our theorem is the following new result. There is an absolute positive constant c such that if n is sufficiently large and 1?q<cn, then every n vertex graph with ⌊n²/4⌋+q edges contains at least

     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Extensions of commutative rings in which trees of prime ideals contract to trees

Résumé  Une extensionA⊂B des anneaux (commutatifs) satisfait à la propriété si tout arbre dans Spec(B) couvre un arbre dans Spec(A). Il est possible qu'une extension entière d'un anneau Noethérien ne satisfait pas à . SiA⊂B soit unei-extension satisfaisante à soit “going-up” soit “going-down”, alorsA⊂B satisfait à . Cependant, une extension d'anneaux satisfaisante à “going-up”, “going-down”, et peut être nonunibranche dans hauteur >1. Un anneau intègreA a le spectre d'un arbre si et seulement siA⊂B satisfait àP pour tout anneau intègreB contenantA (resp., suranneau de BézoutB deA). De plus, si un anneau intègreA n'ait pas de spectre d'un arbre mais soit localement de dimension finie, (par exemple, tout anneau intègre Noethérien de dimension au moins 2), alors il existe un suranneau de BézoutB deA et un arbre saturé dans Spec(B) de sorte que card=4 et l'image de à l'égard de la flèche canonique Spec(B)→Spec(A) est un ensemble saturé tel que card =3 mais n'est pas d'arbre. On donne également des caractérisations associées des classes desi-domaines et des ai-domaines.      

Extensions of commutative rings

In studying the minimal prime spectra of commutative rings with identity we have been able to identify several interesting types of extensions of rings. In particular, we determine what kind of ring extensions will result in a homeomorphisms of the hull-kernel and inverse topologies on the minimal prime spectra. We relate these types of extensions to other known types of extensions.     

On toric face rings

Following a construction of Stanley we consider toric face rings associated to rational pointed fans. This class of rings is a common generalization of the concepts of Stanley-Reisner and affine monoid algebras. The main goal of this article is to unify parts of the theories of Stanley-Reisner and affine monoid algebras. We consider (non-pure) shellable fan’s and the Cohen-Macaulay property. Moreover, we study the local cohomology, the canonical module and the Gorenstein property of a toric face ring.     

Zero-divisor graphs, von Neumann regular rings, and Boolean algebras

For a commutative ring R with set of zero-divisors Z(R), the zero-divisor graph of R is Γ(R)=Z(R)−{0}, with distinct vertices x and y adjacent if and only if xy=0. In this paper, we show that Γ(T(R)) and Γ(R) are isomorphic as graphs, where T(R) is the total quotient ring of R, and that Γ(R) is uniquely complemented if and only if either T(R) is von Neumann regular or Γ(R) is a star graph. We also investigate which cardinal numbers can arise as orders of equivalence classes (related to annihilator conditions) in a von Neumann regular ring.     

Perfect couples of graphs

We generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graphG with a probability distributionP on its vertex set. For any fixedP it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those ofG and its complement G iffG is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality.The research of the authors is partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant No. 1806 resp. No. 1812.     

Triples,current graphs and biembeddings

A family of ladder graphs, used by Youngs in his work on the Heawood conjecture, is used to provide constructions of Skolem and related triple systems, triangular biembeddings of certain complete graphs, and genus embeddings of certain complete multipartite graphs.     

A remark on covering graphs

Every graph G may be transformed into a covering graph either by deletion of edges or by subdivision. Let _E (G) and _V (G) denote corresponding minimal numbers. We prove _E (G) = _V (G) for every graph G.     

Preperfect graphs

We say that a vertexx of a graph is predominant if there exists another vertexy ofG such that either every maximum clique ofG containingy containsx or every maximum stable set containingx containsy. A graph is then called preperfect if every induced subgraph has a predominant vertex. We show that preperfect graphs are perfect, and that several well-known classes of perfect graphs are preperfect. We also derive a new characterization of perfect graphs.