The question of generalizing results involving chordal graphs to similar concepts for chordal bipartite graphs is addressed. First, it is found that the removal of a bisimplicial edge from a chordal bipartite graph produces a chordal bipartite graph. As consequence, occurance of arithmetic zeros will not terminate perfect Gaussian elimination on sparse matrices having associated a chordal bipartite graph. Next, a property concerning minimal edge separators is presented. Finally, it is shown that,...

In this note, precise upper bounds are determined for the minimum degree-sum of the vertices of a 4-cycle and a 5-cycle in a plane triangulation with minimum degree 5: w(C₄) ≤ 25 and w(C₅) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with $w\left(K_{1,4}\right)\le 30$. These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol’ and Madaras.

Define a complete subgraph Q to be simplicial in a graph G when Q is contained in exactly one maximal complete subgraph ('maxclique') of G; otherwise, Q is nonsimplicial. Several graph classes-including strong p-Helly graphs and strongly chordal graphs-are shown to have pairs of peculiarly related new characterizations: (i) for every k ≤ 2, a certain property holds for the complete subgraphs that are in k or more maxcliques of G, and (ii) in every induced subgraph H of G, that same property...

We consider Stanley-Reisner rings $k[x_1,...,x_n]/I\left(\mathscr{H}\right)$ where $I\left(\mathscr{H}\right)$ is the edge ideal associated to some particular classes of hypergraphs. For instance, we consider hypergraphs that are natural generalizations of graphs that are lines and cycles, and for these we compute the Betti numbers. We also generalize some known results about chordal graphs and study a weak form of shellability.

A digraph D is k-transitive if the existence of a directed path (v0, v1, . . . , vk), of length k implies that (v0, vk) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least k. We show...

A signed graph (or sigraph in short) is an ordered pair $S=(S^u,\sigma )$, where $S^u$ is a graph G = (V,E), called the underlying graph of S and σ:E → +, - is a function from the edge set E of $S^u$ into the set +,-, called the signature of S. The ×-line sigraph of S denoted by $L_{\times }\left(S\right)$ is a sigraph defined on the line graph $L\left(S^u\right)$ of the graph $S^u$ by assigning to each edge ef of $L\left(S^u\right)$, the product of signs of the adjacent edges e and f in S. In this paper, first we define semi-total line sigraph and semi-total point sigraph of a given...

Let $R$ be a commutative ring. The annihilator graph of $R$, denoted by $\mathrm{AG}\left(R\right)$, is the undirected graph with all nonzero zero-divisors of $R$ as vertex set, and two distinct vertices $x$ and $y$ are adjacent if and only if ${\mathrm{ann}}_R\left(xy\right)\ne {\mathrm{ann}}_R\left(x\right)\cup {\mathrm{ann}}_R\left(y\right)$, where for $z\in R$, ${\mathrm{ann}}_R\left(z\right)=\{r\in R:rz=0\}$. In this paper, we characterize all finite commutative rings $R$ with planar or outerplanar or ring-graph annihilator graphs. We characterize all finite commutative rings $R$ whose annihilator graphs have clique number $1$, $2$ or $3$. Also, we investigate some properties of the annihilator...

Let G = (V,E) be a graph. A function f : V → {-1,1} is called a bad function of G if ∑u∈NG(v) f(u) ≤ 1 for all v ∈ V where NG(v) denotes the set of neighbors of v in G. The negative decision number of G, introduced in [12], is the maximum value of ∑v∈V f(v) taken over all bad functions of G. In this paper, we present sharp upper bounds on the negative decision number of a graph in terms of its order, minimum degree, and maximum degree. We also establish a sharp Nordhaus-Gaddum-type inequality for...

The main subject of our study are spherical (weakly spherical) graphs, i.e. connected graphs fulfilling the condition that in each interval to each vertex there is exactly one (at least one, respectively) antipodal vertex. Our analysis concerns properties of these graphs especially in connection with convexity and also with hypercube graphs. We deal e.g. with the problem under what conditions all intervals of a spherical graph induce hypercubes and find a new characterization of hypercubes: $G$ is...

A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1, . . . , np) of |V (G)| there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected subgraph of G on ni vertices. Some stronger versions of this property were introduced, namely the ones of being online arbitrarily partitionable and recursively arbitrarily partitionable (OL-AP and R-AP for short, respectively), in which the subgraphs induced by a partition of G must...

A graph is k-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most k. These graphs were introduced by Lick and White in 1970 and have been studied in several subsequent papers. We present sharp bounds on the diameter of maximal k-degenerate graphs and characterize the extremal graphs for the upper bound. We present a simple characterization of the degree sequences of these graphs and consider related results. Considering edge coloring, we conjecture...