An -Problem for location and consensus functions on graphs

详细信息    查看全文

• 作者：F.R. McMorris^a ; ^b ; ^{mcmorris@iit.edu" class="auth_mail" title="E-mail the corresponding author} ; Henry Martyn Mulder^c ; ^{hmmulder@ese.eur.nl" class="auth_mail" title="E-mail the corresponding author} ; Beth Novick^d ; ^{nbeth@clemson.edu" class="auth_mail" title="E-mail the corresponding author} ; Robert C. Powers^b ; ^{robert.powers@louisville.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Median function ; Location function ; Consensus function ; Voting ; Consensus axiom ; ABCABC-Problem
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 July 2016
• 年：2016
• 卷：207
• 期：Complete
• 页码：15-28
• 全文大小：443 K

文摘

A location problem can often be phrased as a consensus problem. The median function class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si2.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=5de685ce1a35f04da17a8181b0c4efad">class="imgLazyJSB inlineImage" height="12" width="30" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15005776-si2.gif">class="mathContainer hidden">class="mathCode">$\mathrm{Med}$ is a location/consensus function on a connected graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si3.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=e3129b62ba2d8aba515c33a77c28a338" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ that has the finite sequences of vertices of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si3.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=e3129b62ba2d8aba515c33a77c28a338" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ as input. For each such sequence class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si5.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=2f6e997633af245afa11933490e694cb" title="Click to view the MathML source">πclass="mathContainer hidden">class="mathCode">$\pi$, class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si2.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=5de685ce1a35f04da17a8181b0c4efad">class="imgLazyJSB inlineImage" height="12" width="30" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15005776-si2.gif">class="mathContainer hidden">class="mathCode">$\mathrm{Med}$ returns the set of vertices that minimize the distance sum to the elements of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si5.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=2f6e997633af245afa11933490e694cb" title="Click to view the MathML source">πclass="mathContainer hidden">class="mathCode">$\pi$. The median function satisfies three intuitively clear axioms: class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si8.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=8d286440f52271ef2418681f1a91c9fd" title="Click to view the MathML source">(A)class="mathContainer hidden">class="mathCode">$\left(A\right)$ Anonymity, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si9.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=8c916922bdee900723e4ff439c86868e" title="Click to view the MathML source">(B)class="mathContainer hidden">class="mathCode">$\left(B\right)$ Betweenness and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si10.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=70a27bcb9dafb5b533ab237a0ec11c77" title="Click to view the MathML source">(C)class="mathContainer hidden">class="mathCode">$\left(C\right)$ Consistency. Mulder and Novick showed in 2013 that on median graphs these three axioms actually characterize class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si2.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=5de685ce1a35f04da17a8181b0c4efad">class="imgLazyJSB inlineImage" height="12" width="30" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15005776-si2.gif">class="mathContainer hidden">class="mathCode">$\mathrm{Med}$. This result raises a number of questions:

class="listitem" id="list_l000005">

class="label">(i)

On what other classes of graphs is class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si2.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=5de685ce1a35f04da17a8181b0c4efad">class="imgLazyJSB inlineImage" height="12" width="30" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15005776-si2.gif">class="mathContainer hidden">class="mathCode">$\mathrm{Med}$ characterized by class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si8.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=8d286440f52271ef2418681f1a91c9fd" title="Click to view the MathML source">(A)class="mathContainer hidden">class="mathCode">$\left(A\right)$, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si9.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=8c916922bdee900723e4ff439c86868e" title="Click to view the MathML source">(B)class="mathContainer hidden">class="mathCode">$\left(B\right)$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si10.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=70a27bcb9dafb5b533ab237a0ec11c77" title="Click to view the MathML source">(C)class="mathContainer hidden">class="mathCode">$\left(C\right)$?

class="label">(ii)

If some class of graphs has other class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=900ed713f43efe8f8d73d54252e16ed0" title="Click to view the MathML source">ABCclass="mathContainer hidden">class="mathCode">$ABC$-functions besides class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si2.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=5de685ce1a35f04da17a8181b0c4efad">class="imgLazyJSB inlineImage" height="12" width="30" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15005776-si2.gif">class="mathContainer hidden">class="mathCode">$\mathrm{Med}$, can we determine additional axioms that are needed to characterize class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si2.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=5de685ce1a35f04da17a8181b0c4efad">class="imgLazyJSB inlineImage" height="12" width="30" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15005776-si2.gif">class="mathContainer hidden">class="mathCode">$\mathrm{Med}$?

class="label">(iii)

In the latter case, can we find characterizations of other functions that satisfy class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si8.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=8d286440f52271ef2418681f1a91c9fd" title="Click to view the MathML source">(A)class="mathContainer hidden">class="mathCode">$\left(A\right)$, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si9.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=8c916922bdee900723e4ff439c86868e" title="Click to view the MathML source">(B)class="mathContainer hidden">class="mathCode">$\left(B\right)$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si10.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=70a27bcb9dafb5b533ab237a0ec11c77" title="Click to view the MathML source">(C)class="mathContainer hidden">class="mathCode">$\left(C\right)$?

We call these questions, and related ones, the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=900ed713f43efe8f8d73d54252e16ed0" title="Click to view the MathML source">ABCclass="mathContainer hidden">class="mathCode">$ABC$-Problem   for consensus functions on graphs. In this paper we present first results. We construct a non-trivial class different from the median graphs, on which the median function is the unique “class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=900ed713f43efe8f8d73d54252e16ed0" title="Click to view the MathML source">ABCclass="mathContainer hidden">class="mathCode">$ABC$-function”. For the second and third question we focus on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si24.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=8fb0db65fc935a7c45787a564438e061" title="Click to view the MathML source">K_nclass="mathContainer hidden">class="mathCode">$K_n$ with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si25.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=68373a426b70366650cdea561b928442" title="Click to view the MathML source">n≥3class="mathContainer hidden">class="mathCode">$n\ge 3$. We construct various non-trivial class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=900ed713f43efe8f8d73d54252e16ed0" title="Click to view the MathML source">ABCclass="mathContainer hidden">class="mathCode">$ABC$-functions amongst which is an infinite family on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005776&_mathId=si27.gif&_user=111111111&_pii=S0166218X15005776&_rdoc=1&_issn=0166218X&md5=300aa03b4ac81fc8e1a4a96b23e4b334" title="Click to view the MathML source">K₃class="mathContainer hidden">class="mathCode">$K_3$. For some nice families we present a full axiomatic characterization.