N.M. Stat. § 14-11-2
Any and every legal notice or advertisement shall be published in a daily, tri-weekly, a semi-weekly or a weekly newspaper of general circulation that can be obtained by single copy and that is entered under the second class postage privilege in the county in which the notice or advertisement is required to be published; which newspaper, if published tri-weekly, semi-weekly or weekly, shall have been so published in the county continuously and uninterruptedly during the period of at least twenty-six consecutive weeks next prior to the first issue thereof containing any such notice or advertisement, and which newspaper, if published daily, shall have been so published in the county uninterruptedly and continuously during the period of at least six months next prior to the first issue thereof containing any such notice or advertisement; provided that the mere change in the name of any newspaper or the removal of the principal business office or seat of publication of any newspaper from one place to another in the same county shall not break or affect the continuity in the publication of any such newspaper if the newspaper is in fact continuously and uninterruptedly printed and published within the county as provided in this section; provided further that a newspaper shall not lose its rights as a legal publication if it fails to publish one or more of its issues by reason of fire, flood, accident, transportation embargo or tie-up or other casualty beyond the control of the publisher; provided further that any legal notice which fails of publication for the required number of insertions by reasons beyond the control of the publisher shall not be declared illegal if the publication has been made in one issue of the publication; and provided further that if in any county in this state there has not been published any newspaper for the prescribed period at the time when any such notice or advertisement is required to be published, the notice or advertisement may be published in any newspaper having a general circulation or published and printed in whole or in part in that county and that can be obtained by single copy in that county.
NMS § 14-11-2