Graphs in which all maximal bipartite subgraphs have the same order
- PDF / 419,781 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 39 Downloads / 216 Views
Aequationes Mathematicae
Graphs in which all maximal bipartite subgraphs have the same order Wayne Goddard, Kirsti Kuenzel, and Eileen Melville
Abstract. Motivated by the concept of well-covered graphs, we define a graph to be wellbicovered if every vertex-maximal bipartite subgraph has the same order (which we call the bipartite number). We first give examples of them, compare them with well-covered graphs, and characterize those with small or large bipartite number. We then consider graph operations including the union, join, and lexicographic and cartesian products. Thereafter we consider simplicial vertices and 3-colored graphs where every vertex is in triangle, and conclude by characterizing the maximal outerplanar graphs that are well-bicovered. Mathematics Subject Classification. 05C69. Keywords. Well-covered graph, Bipartite subgraph, Maximal.
1. Introduction Plummer [4] defined a graph to be well-covered if every maximal independent set is also maximum. That is, a graph is well-covered if every maximal independent set has the same cardinality, namely the independence number α(G). Much has been written about these graphs. For example, Ravindra [6] characterized well-covered bipartite graphs, Campbell, Ellingham, and Royle [1] characterized well-covered cubic graphs, and Finbow, Hartnell, and Nowakowski [2] characterized well-covered graphs of girth 5 or more. Motivated by this idea, we define a graph to be well-bicovered if every vertex-maximal bipartite subgraph has the same order. Equivalently, one can define the bipartite number of a graph G, denoted b(G), as the maximum cardinality of a bipartite induced subgraph in G. (We will henceforth just assume that subgraph means induced subgraph.) Then, being well-bicovered means all maximal bipartite subgraphs have cardinality b(G). The problem of finding a maximum bipartite subgraph is well-studied. For instance, Zhu [8]
W. Goddard et al.
AEM
showed that any triangle-free subcubic graph G with order n has b(G) ≥ 57 n, and the Four Color Theorem shows that b(G) ≥ n/2 for any planar graph G. In this paper, we introduce and study well-bicovered graphs. We give examples and compare well-bicovered graphs with well-covered graphs, and characterize well-bicovered graphs with small or large bipartite numbers. We then consider their relationship to graph operations including the union, join, and lexicographic and cartesian products. Thereafter we consider 3-colorable graphs and simplicial vertices, and conclude by characterizing the maximal outerplanar graphs that are well-bicovered.
1.1. Definitions and terminology Let G = (V (G), E(G)) be a simple, finite graph of order n(G) = |V (G)|. The open neighborhood of a vertex v ∈ V (G) is N (v) = { x ∈ V (G) : xv ∈ E(G) }. The degree of v ∈ V (G) is deg(v) = |N (v)|, and the maximum degree of G is denoted Δ(G). Given a set X ⊆ V (G), we let G[X] represent the subgraph induced by X. If degG (x) = 1, we refer to x as a leaf in G, and the edge incident with x as a pendant edge. In general, a bridge is an edge whose removal
Data Loading...
