The -metric dimension of the lexicographic product of graphs

详细信息    查看全文

• 作者：Alejandro Estrada-Moreno^a ; ^{alejandro.estrada@urv.cat" class="auth_mail" title="E-mail the corresponding author} ; Ismael G. Yero^b ; ^{ismael.gonzalez@uca.es" class="auth_mail" title="E-mail the corresponding author} ; Juan A. Rodrí ; guez-Velá ; zquez^a ; ^{juanalberto.rodriguez@urv.cat" class="auth_mail" title="E-mail the corresponding author}
• 关键词：kk-metric generator ; kk-metric dimension ; kk-adjacency dimension ; Lexicographic product graphs
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 July 2016
• 年：2016
• 卷：339
• 期：7
• 页码：1924-1934
• 全文大小：456 K

文摘

Given a simple and connected graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si7.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=5fce0f82341cabbca2991656a4c0b3b2" title="Click to view the MathML source">G=(V,E)class="mathContainer hidden">class="mathCode">$G=(V,E)$, and a positive integer class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$, a set class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=2f7c4603bb12db30923b3906d7ede990" title="Click to view the MathML source">S⊆Vclass="mathContainer hidden">class="mathCode">$S\subseteq V$ is said to be a class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-metric generator for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si11.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=35b44d361cccb11feaf47433e45ab344" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$, if for any pair of different vertices class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si12.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=4dbbd476e748a770429f7d96aa1a160c" title="Click to view the MathML source">u,v∈Vclass="mathContainer hidden">class="mathCode">$u,v\in V$, there exist at least class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ vertices class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si14.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=c9b33ab991ed05ec509ea16189295c8d" title="Click to view the MathML source">w₁,w₂,…,w_k∈Sclass="mathContainer hidden">class="mathCode">$w_1,w_2,\dots ,w_k\in S$ such that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si15.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=ab16e4cddec231601534f902217939f4" title="Click to view the MathML source">d_G(u,w_i)≠d_G(v,w_i)class="mathContainer hidden">class="mathCode">$d_G(u,w_i)\ne d_G(v,w_i)$, for every class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si16.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=423e839ead72aea6933b717114a44786" title="Click to view the MathML source">i∈{1,…,k}class="mathContainer hidden">class="mathCode">$i\in \{1,\dots ,k\}$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si17.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=7da3bcf1dabd9f074d807f2d17c918ae" title="Click to view the MathML source">d_G(x,y)class="mathContainer hidden">class="mathCode">$d_G(x,y)$ denotes the distance between class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si18.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=5f3967af71dc45417e5a34a99fe0ef2b" title="Click to view the MathML source">xclass="mathContainer hidden">class="mathCode">$x$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si19.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=b0f27931788ab20b056ccacae6b61c57" title="Click to view the MathML source">yclass="mathContainer hidden">class="mathCode">$y$. The minimum cardinality of a class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-metric generator is the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-metric dimension of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si11.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=35b44d361cccb11feaf47433e45ab344" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$. A set class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si9.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=2f7c4603bb12db30923b3906d7ede990" title="Click to view the MathML source">S⊆Vclass="mathContainer hidden">class="mathCode">$S\subseteq V$ is a class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-adjacency generator for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si11.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=35b44d361cccb11feaf47433e45ab344" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ if any two different vertices class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si26.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=4db6a725c98991757f963ecbb9ba7b48" title="Click to view the MathML source">x,y∈V(G)class="mathContainer hidden">class="mathCode">$x,y\in V\left(G\right)$ satisfy class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si27.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=be27252675b5ef486cc7590077602bb4">class="imgLazyJSB inlineImage" height="15" width="235" 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-S0012365X15004653-si27.gif">class="mathContainer hidden">class="mathCode">$|(\left(N_G\left(x\right)▿N_G\left(y\right)\right)\cup \{x,y\})\cap S|\ge k$, where class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si28.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=a8f11d614b2e4b8b795acee7089e302a">class="imgLazyJSB inlineImage" height="15" width="91" 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-S0012365X15004653-si28.gif">class="mathContainer hidden">class="mathCode">$N_G\left(x\right)▿N_G\left(y\right)$ is the symmetric difference of the neighborhoods of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si18.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=5f3967af71dc45417e5a34a99fe0ef2b" title="Click to view the MathML source">xclass="mathContainer hidden">class="mathCode">$x$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si19.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=b0f27931788ab20b056ccacae6b61c57" title="Click to view the MathML source">yclass="mathContainer hidden">class="mathCode">$y$. The minimum cardinality of any class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-adjacency generator is the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-adjacency dimension of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si11.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=35b44d361cccb11feaf47433e45ab344" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$. In this article we obtain tight bounds and closed formulae for the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-metric dimension of the lexicographic product of graphs in terms of the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004653&_mathId=si6.gif&_user=111111111&_pii=S0012365X15004653&_rdoc=1&_issn=0012365X&md5=3ea2e3cb7b081de0e78e769a3ee78e5a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-adjacency dimension of the factor graphs.