Morten H. Nielsen1, Ortrud R. Oellermann*2
1Department. of Mathematics and Statistics, Thompson Rivers University 900 McGill Road, Kamloops, BC, Canada
2Department of Mathematics and Statistics, University of Winnipeg 515 Portage Avenue, Winnipeg, MB, R3B 2E9, Canada
Abstract:

Let \( G \) be a connected graph and let \( U \) be a set of vertices in \( G \). A \emph{minimal \( U \)-tree} is a subtree \( T \) of \( G \) that contains \( U \) and has the property that every vertex of \( V(T) – U \) is a cut-vertex of \( \langle V(T) \rangle \). The \emph{monophonic interval} of \( U \) is the collection of all vertices of \( G \) that lie on some minimal \( U \)-tree. A set \( S \) of vertices of \( G \) is \( m_k \)-\emph{convex} if it contains the monophonic interval of every \( k \)-subset \( U \) of vertices of \( S \). Thus \( S \) is \( m_2 \)-convex if and only if it is \( m \)-convex.

In this paper, we consider three local convexity properties with respect to \( m_3 \)-convexity and characterize the graphs having either property.

William Kocay1
1St. Paul’s College, Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada, R3T 2N2
Abstract:

Let \( G \) and \( H \) be graphs on \( n+2 \) vertices \( \{u_1, u_2, \ldots, u_n, x, y\} \) such that \( G – u_i \cong H – u_i \), for \( i = 1, 2, \ldots, n \). Recently, Ramachandran, Monikandan, and Balakumar have shown in a sequence of two papers that if \( n \geq 9 \), then \( |\varepsilon(H) – \varepsilon(G)| \leq 1 \). In this paper, we present a simpler proof of their theorem, using a counting lemma.

E-mail Alert

Add your e-mail address to receive upcoming issues of Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC).

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;