Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
- Publication
- Publication Type
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Cyclic Matching Sequencibility Of Graphs, Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder
Cyclic Matching Sequencibility Of Graphs, Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder
Mathematics Faculty Research
We define the cyclic matching sequencibility of a graph to be the largest integer d such that there exists a cyclic ordering of its edges so that every d consecutive edges in the cyclic ordering form a matching. We show that the cyclic matching sequencibility of K2m and K2m+1 equals m − 1.
Extremal Problems For Roman Domination, E. W. Chambers, W. Kinnersley, N. Prince, D. B. West
Extremal Problems For Roman Domination, E. W. Chambers, W. Kinnersley, N. Prince, D. B. West
Noah Prince
A Roman dominating function of a graph G is a labeling f: V(G) →{0,1,2} such that every vertex with a label 0 has a neighbor with label 2. The Roman domination number γR(G) of G is the minimum of ∑ʋϵV(G)f(v) over such functions. Let G be a connected n-vertex graph. We prove that γR(G) ≤ 4n/5, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for γR(G) + …