The H-linked degree-sum parameter for special graph families

East Kenney, Lydia; Powell, Jeffrey

doi:10.2140/involve.2017.10.707

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

The $H$-linked degree-sum parameter for special graph families

Lydia East Kenney and Jeffrey Scott Powell

Vol. 10 (2017), No. 4, 707–720

DOI: 10.2140/involve.2017.10.707

Abstract

For a fixed graph $H$ , a graph $G$ is $H$ -linked if any injection $f : V (H) \to V (G)$ can be extended to an $H$ -subdivision in $G$ . The concept of $H$ -linked generalizes several well-known graph theory concepts such as $k$ -connected, $k$ -linked, and $k$ -ordered. In 2012, Ferrara et al. proved a sharp $σ_{2}$ (or degree-sum) bound for a graph to be $H$ -linked. In particular, they proved that any graph $G$ with $n > 20 | E (H) |$ vertices and $σ_{2} (G) \geq n + a (H) - 2$ is $H$ -linked, where $a (H)$ is a parameter maximized over certain partitions of $V (H)$ . However, they do not discuss the calculation of $a (H)$ in their work. In this paper, we prove the exact value of $a (H)$ in the cases when $H$ is a path, a cycle, a union of stars, a complete graph, and a complete bipartite graph. Several of these results lead to new degree-sum conditions for particular graph classes while others provide alternate proofs of previously known degree-sum conditions.

Keywords

H-linked, path, cycle, degree-sum, Ore condition

Mathematical Subject Classification 2010

Primary: 05C35, 05C38

Secondary: 05C83

Milestones

Received: 5 May 2016

Revised: 1 July 2016

Accepted: 11 July 2016

Published: 7 March 2017

Communicated by Jerrold Griggs

Authors

Lydia East Kenney
Smiths Station High School 4228 Lee Rd. 430 Smiths Station, AL 36877 United States

Jeffrey Scott Powell
Department of Mathematics and Computer Science Samford University 800 Lakeshore Drive Birmingham, AL 35229 United States

Vol. 10, No. 4, 2017